首页 > 代码库 > Cmpletepack coming~^.^

Cmpletepack coming~^.^

昨天小小总结了01背包:01背包 不足之处还望多提意见~噶呜~

今天来总结一下完全背包:

完全背包:

   基本思路:类似于01背包,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,策略已经不是取与不取两种,而是取0件,取1件,..等很多种,如果仍按01背包的思路,令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值,仍可按照每种物品的不同策略写出状态转移方程,like this:f[i][v]=max(f[i-1][v-k*c[i]]+k*w[i]);

 1      for i←1 to N 2  3          do for j←1 to V 4  5              do for k←0 to j/C[i] 6  7                 if(j >= k*C[i]) 8  9                      then F[i][k] ← max(F[i][k],F[i-1][j-k*C[i]]+k*W[i])10 11      return F[N][V]

 

 

 

一个简单的优化:

    若两件物品i,j满足c[i]<=c[j]&&w[i]>=w[j],则将物品j去掉不用考虑。 这个筛选过程如下:先找出体积大于背包的物品直接筛掉一部分(也可能一种都筛不掉)复杂度O(N)。利用计数排序思想对剩下的物品体积进行排序,同时筛选出同体积且价值最大的物品留下,其余的都筛掉(这也可能一件都筛不掉)复杂度O(V)。整个过程时间复杂度为O(N+V)

转化成01背包问题求解:

    因为同种物品可以多次选取,那么第i种物品最多可以选取V/C[i]件价值不变的物品,然后就转化为01背包问题。整个过程的时间复杂度并未减少。如果把第i种物品拆成体积为C[i]×2k价值W[i]×2k的物品,其中满足C[i]×2k≤V。那么在求状态F[i][j]时复杂度就变为O(log2(V/C[i]))。整个时间复杂度就变为O(NVlog2(V/C[i]))

时间复杂度优化为O(NV)的算法:

    这个算法使用一维数组:

for i:1 to N

    do for v:0 to V

        do f[v]=max{f[v],f[v-cost]+weight}

    你会发现这个伪代码和01背包的伪代码只有v循环次序不同,为什么01背包要按照V=v~0来循环呢?这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来,这正是为了每件物品只选一次保证在考虑“选入第i件物品”这件策略时依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]],而现在完全背包的特点是每件物品可选无数件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i件物品的子结果:f[i][v-c[i]]. 

值得一提:

    上面伪代码的两层for循环的次序可以颠倒,这个结论可能回来来算法时间常数上的优化。

总结:完全背包也是相当基础的背包问题,有上述两个状态转移方程。吾不才,希望多提意见~噶呜~