背包问题 ,所不同的是每种物品有无限件。也就是从
每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取 0 件、
取 1 件、取 2 件……等很多种。如果仍然按照解 01 背包时的思路,令 f[i][v]
表示前 i 种物品恰放入一个容量为 v 的背包的最大权值。仍然可以按照每种物
品不同的策略写出状态转移方程,像这样:
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
这跟 01 背包问题一样有 O(VN)个状态需要求解,但求解每个状态的时间已经
不是常数了,求解状态 f[i][v]的时间是 O(v/c[i]),总的复杂度可以认为是
O(V*Σ(V/c[i])),是比较大的。
将 01 背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说明 01
背包问题的方程的确是很重要,可以推及其它类型的背包问题。但我们还是试
图改进这个复杂度。
一个简单有效的优化
完全背包问题有一个很简单有效的优化,是这样的:若两件物品 i、j 满足
c[i]<=c[j]且 w[i]>=w[j],则将物品 j 去掉,不用考虑。这个优化的正确性显
然:任何情况下都可将价值小费用高得 j 换成物美价廉的 i,得到至少不会更差
的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加
快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据
可以一件物品也去不掉。
这个优化可以简单的 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。这是二进制的思想,因为不管最