(发现代码有bug,赶紧编辑掉-----逃)~

[此贴子已经被作者于2017-12-25 20:45编辑过]

二进制说到底就是穷举?~对于数目不多的稀疏背包还是好用的~
当然这里我用到了动态规划,我这个逻辑推敲应该没有问题的,当然细节处理上面还可以完善一下~

其实这个我理解花了很长时间的,打算简单讲解一下做法,不过发现我擅长理解不擅长解释~

[此贴子已经被作者于2017-12-25 15:59编辑过]

0-1背包,完全背包,多重背包,混合背包感觉到底还是同一个东西,就是数目的取值不同而已,广义来说我这种解法同样适用于最广义的混合背包,把相同的类型合并一下就可以了,算法内容不用怎么变~

[此贴子已经被作者于2017-12-25 16:00编辑过]

0-1背包动态规划也可以理解成回溯思想~

回溯和一般递归不同的地方就是一般递归每次递归开个新栈都是依赖于上一个的状态提供的参数~

然而回溯就是当发现递归走过的路是曾经走过的时候就直接利用上一次的状态而不是直接开个新栈~

当然这就涉及到搜索了,要检查新的空间状态是否在状态空间树里面(当然这里可以理解成一个简单的哈希表,状态空间树可以理解为树型结构,当然需要o(log(n))的搜索时间的,不过却可以省去没有被利用的空间,对于稀疏背包还是很好用的,但对于过于稀疏的背包还是直接二进制枚举方便)这也是要开一个数组保留数据的原因(网上搜过dp动态规划很多用二维数组输出路径,这个对重量经过qsort排序后dp的时候可以解决避免重复选取问题,在这里一维已经够用了)~

[此贴子已经被作者于2017-12-25 16:10编辑过]

算法基于原理,从原理出发,看看为什么动态dp到底能够省时,其实当重量为k时有n种组合,1+5+9=15和3+5+6=15这两个15是否是同一个东西呢,在普通递归算法这两个是不同的"15"虽然它的值一样,但回溯算法或者动态dp认为这两个"15"本来就是同一个东西,第二次搜到15的时候直接利用第一次出现"15"的状态就可以了~

当然如果数稀疏背包每个数字出现的频数比较少的时候这算法局会慢慢变成传统的枚举算法了~

通常情况下背包的最大容量会比所有组合数少很多,那意味着什么呢,意味着同一个k值存在很多不同的组合,由于每个相同的k值拥有同一种状态或者叫合并成同一个k值,所以这就是动态规划或者回溯能够优化的地方~

[此贴子已经被作者于2017-12-25 16:28编辑过]

我还不是大神好嘛(当然说我小神我还是可以恭维的)记得以前论坛曾经出现过很多指导过我的大神级人物

其中印象最深刻的几个

@azzbcc
@xzlxzlxzl
@寒风中的细雨

以及现在活跃的rjsp和吹水佬也是很值得一提的~

总之,我感觉自己还有很大发展空间,这包包问题才刚刚开始呢,真的要拓展的可以联系到其它很多东西的~

[此贴子已经被作者于2017-12-25 16:36编辑过]

这个我了解过一下,在我来论坛之前真正意义上算法方面的神级人物,现阶段的水平对于他来说不值得一提~
或者我还可以从他身上学到很多~

题外话……我读大二(还在学习数据结构),工作方面我暂时也没有为自己做过什么安排……当然有兴趣的短信私聊一下我还是可以的~

话说,感觉你还真的了不起耶,可以和他见面,或者他是算法领域某位比较有影响力的大牛吧,或者有兴趣的还可以一起学习一下算法,或者再学下去就可以弄ACM了(记得某同学推荐我明年参加蓝桥杯,虽然感觉ACM比蓝要专业化一些,不过我这个水平蓝我还是感觉比较勉强的,毕竟站在一个高端平台上接触到的大神多了就是这样)~

诶,我那个bug在运行结果问题,不容易发现的,不编辑掉的话别人不知道岂不是坑人家了……我知道bug原因了到底还是逻辑问题,打算找个时间来修复一下感觉这次写出来的或者会很像网上搜到的代码了~