题目：
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路：
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物 品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
优化空间复杂度：
以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环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-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1] [v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态 f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。
来看一个题目：
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
上面的1~10是背包为相应容量时的最大价值！
首先要明确这张表是至底向上，从左到右生成的。
如果物品n的重要超过背包允许的总重量，则物品n不放入背包，此时背包中物品的总价值为0，否则，如果物品n装入背包后不超重，则装入物品n，此时背包的总价值为物品n的价值v[n]。
因为W(e)为4，当背包容量volume小于W(e)时不能放入，所以当前的背包总价值都为0.当volume>=W(e)时，物品e可以放入背包，此时当前的背包总价值都为V(e).
后面的以此类推，来看下右上角的15是怎么来的，我们把其看做m(1,10)。
m(1,10) = max(m(2,10),m(2,(10-2))+6)=max(11,15)=15.
编写代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <iostream> using namespace std; int bag[12900]; int w[3410],v[3410]; void main(void) { int n,m,i,k; cin >> n >> m; //背包数、 总容量 for(i=1; i<=n; i++) cin >> w[i] >> v[i]; //背包容量、 背包价值 memset(bag,0,sizeof(bag)); for(i=1; i<=n; i++) { for(k=m; k>=w[i]; k--){ if( bag[k-w[i]]+ v[i] > bag[k] ){ bag[k] = bag[k-w[i]]+ v[i]; } cout<<bag[k]<<"\t"; } cout<<endl; } cout << bag[m] << endl; } |
输入数据：
5 10
4 6
5 4
6 5
2 3
2 6
运行结果：
大家可以在POJ上刷刷类似的题目，像POJ3624就是一个最简单的0-1背包问题。