给定一些物品和他们的价值v， w
背包总容量C 求背包能获得的最大价值
1. 不一定装满 只考虑最大价值
状态转移方程
if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
else f[i][j] = f[i - 1][j];
if的作用是防止装入比当前背包容量还大的物品
方程用来判断是否装入当前的物品
（用总容量减去当前物品体积 剩余的容量在前面物品中找出最大价值 比较拿或不拿当前物品得到的价值）
初始化为 f[0][0] = 0;
2. 一定装满
只需要在1的代码里初始化加上一句即可
for(int i = 1; i <= C; i++)
f[0][i] = -(1 << 30);
(初始化为负无穷， 就可以把背包未装满情况去掉
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 const int MaxN = 1e3; 8 int n, m, v[MaxN + 5], w[MaxN + 5], f[MaxN + 5][MaxN + 5], C; 9 10 11 int main() 12 { 13 scanf("%d %d", &n, &C); 14 for (int i = 1; i <= n; i++) 15 { 16 scanf("%d", &v[i]); 17 scanf("%d", &w[i]); 18 } 19 f[0][0] = 0; 20 for (int i = 1; i <= C; i++) 21 f[0][i] = -(1 << 30);// 这句去掉则不考虑恰好装满 22 for (int i = 1; i <= n; i++) 23 { 24 for (int j = 0; j <= C; j++) 25 { 26 if (j >= v[i]) 27 f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); 28 else f[i][j] = f[i - 1][j]; 29 } 30 } 31 if (f[n][C] < 0) printf("Error\n"); 32 else printf("%d\n", f[n][C]); 33 34 }
)
原文：http://www.cnblogs.com/wns0108/p/4999791.html