错的一种方法是:首先将费用大于 V 的物品去掉,然后使用类似计数排序的做法,计算出
费用相同的物品中价值最高的是哪个,可以 O(V+N)地完成这个优化。这个不太重要的过
程就不给出伪代码了,希望你能独立思考写出伪代码或程序。
转化为 01 背包问题求解
既然 01 背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为 01 背包
问题来解。最简单的想法是,1.考虑到第 i 种物品最多选 V/c[i]件,于是可以把第 i 种物品
转化为 V/c[i]件费用及价值均不变的物品,然后求解这个 01 背包问题。这样完全没有改进
基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为 01 背包问题的思路:将
一种物品拆成多件物品。
更高效的转化方法是:把第 i 种物品拆成费用为 2 . c[i]*2^k、价值为 w[i]*2^k 的若干件物
品,其中 k 满足 c[i]*2^k<=V。这是二进制的思想,因为不管最优策略选几件第 i 种物品,
总可以表示成若干个 2^k 件物品的和。这样把每种物品拆成 O(log V/c[i])件物品,是一个很
大的改进。
但我们有更优的 O(VN)的算法。
O(VN)的算法
这个算法使用一维数组,先看伪代码:
3
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
你会发现,这个伪代码与 P01
的伪代码只有 v 的循环次序不同而已。为什么这样一改就可
行呢?首先想想为什么 P01 中要按照 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 循环的次序可以颠倒。这个结论有可能会带来算
法时间常数上的优化。