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])；

      for i← to N

          do for j← to V

              do for k← to j/C[i]

                 if(j >= k*C[i])

                      then F[i][k] ← max(F[i][k],F[i-][j-k*C[i]]+k*W[i])

      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]×2^k价值W[i]×2^k的物品，其中满足C[i]×2^k≤V。那么在求状态F[i][j]时复杂度就变为O(log₂(V/C[i]))。整个时间复杂度就变为O(NVlog₂(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循环的次序可以颠倒，这个结论可能回来来算法时间常数上的优化。

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

巴特西

Cmpletepack coming~^.^

最新文章

热门文章