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

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

0 1背包我记得有两种解发，一个二进制，一个动态规划，大学时候写过，现在不会写了

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

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

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

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

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

二进制是数目有限的，确实属于暴力算法。
我当初也理解过动态规划，也花了好长时间。
个人感觉动态规划这种高级算法在实际工作中用的不是很多，不过基础算法确实是有点用。

我玩算法玩的不是很6，只是在大学时候刷过几个OJ的题，只是会一些基本的，高级的只能说是听说过

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编辑过]

虽然看不太懂，但是能感觉到你对理解很深刻，以后有算法上的问题就问你了