完全背包问题

看这篇日志之前，请先阅读我的上一篇日志，关于0/1背包的问题。

完全背包问题的描述：

有N 种物品和一个容量为V 的背包，每种物品都有无限件可用。第i 种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

可能大家已经看出来了，完全背包问题其实就是在0/1背包的问题的基础上加了一个条件：每种物品都有无限件可用。

这个问题有不少解法，下面只给出最优化的O(VN)的算法。
这个算法使用一维数组，先看伪代码：
for i=1..N
for v=0..V
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]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。值得一提的是，上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
这个算法也可以以另外的思路得出。

例如，将基本思路中求解f[i][v-c[i]]的状态转移方程显式地写出来：

f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

把[i-1]和[i] 都去掉，就可以得到f[v]=max{f[v],f[v-c[i]]+w[i]}。为什么可以去掉呢。看一下上一篇日志中的这个图

 
你会发现，我们用二维数组 的解法做的时候，都是扣掉 当前的容量所剩下的容量最多能放多少，取的是上一行的数据： f[i-1][v]，这是因为在当前背包加入的之前，上一行就表示出了 加入上一个背包时的最优解。而其实每一行都比上一行优化，因为每往下走一行，就加入了一个背包，比原来的选择多，得出的优化值自然比上一行的优化。

知道了每一行都比上一行优化之后 ，完全背包问题的答案就可以得出来了，我们每次都取当前行，即f[i][v]，那么原状态方程就变成了：f[i][v]=max{f[i][v],f[i][v-c[i]]+w[i]}，呵呵，二维数组的第一维都变成i了，就是说都在同一行进行比较了。这样的话就可以把它转化成一维数组问题了。即，直接把[i]去掉。。。

最后抽象出处理一件完全背包类物品的过程伪代码：
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}

 

上传了一个参考文档，有兴趣的同志可以自己去看看

 

评论

1 楼 javafound 2011-03-30  

图片毛出来啊