这个优化可以简单的 O(N^2)地实现,一般都可以承受。另外,针对背包问题
而言,比较不错的一种方法是:首先将费用大于 V 的物品去掉,然后使用类似
计数排序的做法,计算出费用相同的物品中价值最高的是哪个,可以 O(V+N)
地完成这个优化。这个不太重要的过程就不给出伪代码了,希望你能独立思考
写出伪代码或程序。
转化为 01 背包问题求解
既然 01 背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转
化为 01 背包问题来解。最简单的想法是,考虑到第 i 种物品最多选 V/c[i]件,
于是可以把第 i 种物品转化为 V/c[i]件费用及价值均不变的物品,然后求解这个
01 背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将
完全背包问题转化为 01 背包问题的思路:将一种物品拆成多件物品。
更高效的转化方法是:把第 i 种物品拆成费用为 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)的算法
这个算法使用一维数组,先看伪代码:
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 的顺序循环。这就是这个简单的程序为何成立的道
理。
这个算法也可以以另外的思路得出。例如,基本思路中的状态转移方程可以等
价地变形成这种形式:
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
将这个方程用一维数组实现,便得到了上面的伪代码。