//详解来自《背包问题九讲》崔添翼(Tianyi Cui) 2011-09-28
1 01 背包问题
1.1 题目有 N 件物品和一个容量为 V 的背包。放入第 i件物品耗费的费用是 Ci1，得到的价值是 Wi。求解将哪些物品装入背包可使价值总和最大。1.2 基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即 F [ i, v ] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是：F [ i, v ] = max {F [i − 1, v ], F [i − 1, v − Ci ] + Wi }这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只和前 i − 1 件物品相关的问题。如果不放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入容量为 v 的背包中”，价值为 F [i − 1, v ]；如果放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − Ci 的背包中”，此时能获得的最大价值就是 F [i − 1, v − Ci ] 再加上通过放入第 i 件物品获得的价值 Wi。伪代码如下：F [0, 0..V ] ← 0for i ← 1 to Nfor v ← 0 to Ci − 1F [i, v ] ← F [i − 1, v ]for v ← Ci to VF [i, v ] ← max {F [i − 1, v ], F [i − 1, v − Ci ] + Wi }1.3 优化空间复杂度以上方法的时间和空间复杂度均为 O (V N )，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到 O (V )。先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i ← 1 . . . N，每次算出来二维数组 F [i, 0 . . . V ] 的所有值。那么，如果只用一个数组 F [0 . . . V ]，能不能保证第 i次循环结束后 F [v ] 中表示的就是我们定义的状态 F [i, v ] 呢？ F [i, v ] 是由 F [i − 1, v ] 和F [i − 1, v − Ci ] 两个子问题递推而来，能否保证在推 F [i, v ] 时（也即在第 i 次主循环中推 F [v ] 时）能够取用 F [i − 1, v ] 和 F [i − 1, v − Ci ] 的值呢？事实上，这要求在每次主循环中我们以 v ← V . . . 0 的递减顺序计算 F [v ]，这样才能保证计算 F [v ] 时 F [v − Ci ] 保存的是状态 F [i − 1, v − Ci ] 的值。伪代码如下：1也即占用背包的空间容量，后文统一称之为“费用 (cost)”3F [0 ..V ] ← 0for i ← 1 to Nfor v ← V to CiF [ v ] ← max {F [v ], F [v − Ci ] + Wi }其中的 F [v ] ← max {F [v ], F [v − Ci ] + Wi } 一句，恰就对应于我们原来的转移方程，因为现在的 F [v − Ci ] 就相当于原来的 F [i − 1, v − Ci ]。如果将 v 的循环顺序从上面的逆序改成顺序的话，那么则成了 F [i, v ] 由 F [i, v − Ci ] 推导得到，与本题意不符。事实上，使用一维数组解 01 背包的程序在后面会被多次用到，所以这里抽象出一个处理一件 01 背包中的物品过程，以后的代码中直接调用不加说明。def ZeroOnePack(F, C, W)for v ← V to CF [v ] ← max (F [v ], f [v − C ] + W )有了这个过程以后， 01 背包问题的伪代码就可以这样写：F [0..V ] ← 0for i ← 1 to NZeroOnePack(F, Ci, Wi)1.4 初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法，要求恰好装满背包，那么在初始化时除了 F [0] 为 0，其它F [1..V ] 均设为 −∞，这样就可以保证最终得到的 F [V ] 是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 F [0..V ]全部设为 0。这是为什么呢？可以这样理解：初始化的 F 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0了。这个小技巧完全可以推广到其它类型的背包问题，后面不再对进行状态转移之前的初始化进行讲解。1.5 一个常数优化上面伪代码中的for i ← 1 to Nfor v ← V to Ci4中第二重循环的下限可以改进。它可以被优化为for i ← 1 to Nfor v ← V to max ( V − Σ Ni Wi,Ci )这个优化之所以成立的原因请读者自己思考。（提示：使用二维的转移方程思考较易。）1.6 小结01 背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想。另外，别的类型的背包问题往往也可以转换成 01 背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及空间复杂度怎样被优化。
//HDU 2602#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int h[1005];int v[1005];int main (){ int t,n,m,l; int f[1005]; scanf("%d",&t); while (t--) { scanf("%d%d",&n,&m); for (int i = 1; i <= n; i++) scanf("%d",&v[i]); for (int i = 1; i <= n; i++) scanf("%d",&h[i]); memset(f,0,sizeof(f)); for (int i = 1; i <= n; i++) {// for(int j = m; j >= h[i]; j--)//j是放入物品i之后的容量 f[j] = max(f[j],f[j-h[i]]+v[i]); } PRintf("%d/n",f[m]); } return 0;}
新闻热点
疑难解答
