01背包问题

问题背景：
设有容量为V的背包，有N种物品，每件物品的体积是c[i]，对应的价值是v[i]，每种物品只有一个，要使背包中所装物品的价值总和最大，问该如何选择。
用一个二维数组f[i][j]，来表示i件物品，在用j的容量时的最大的价值。因为对于每一件物品，你选择就只能是装或者不装这件物品。
例如：
物品： a b c d
体积： 5 4 6 10
价值; 10 7 14 25
当你背包装1件物品时，假如你的背包容量为4，此时f[1][4]=7,你只能装物品b，如果你背包容量为9，这时你就有了选择，能够装下物品a，b，c中的任何一个，因为只能装下一件物品，所以即使你能装下a和b，你当然也只能选价值最大的物品c，即f[1][9]=14。
第一件物品当然是比较简单，当背包装两件物品时（i=2），当你背包还能装下第二件物品，此时你有两个选择，对第二件物品拿与不拿：
拿的话就是f[i][j] = f[i-1][j – c[i]] + v[i] 下划线部分是拿第i个物品之前最多能拿的价值，再加上v[i]（第i个物品的价值）这就是拿第i个物品时的最大价值。
不拿的话就是f[i][j] = f[i-1][j]就相当于装i-1件物品的最大价值。当你背包装不下第二件物品的时候也是f[i][j] = f[i-1][j]（装不下了，还不是只能像前面一样呗）
这时，我们每一步都是取的最佳方案（得到了最大价值）
我们就可以得出状态转移方程 f[i][j] = max(f[i-1][j], f[i-1][j – c[i]] + v[i])
目标就是f[N][V]
这里有个难理解的地方就是初学者可能认为，f[i][j] = f[i-1][j – c[i]] + v[i]不是装得下就装了吗？
并不是这样！！！ 当你的背包容量V = 26时
我们不如打个表看看

比如f[3][25] = max(f[2][25], f[2][25-6] + 14) = max(39, 56)=56 这就不对了 为什么呢？！
比如f[4][25] = max(f[3][25], f[3][25-10] + 25) = max(49,56)=56; 这又是对的
但是！！！ 程序出来是这样的

在这里
比如f[3][25] = max(f[2][25], f[2][25-6] + 14) = max(17, 31)=31
比如f[4][25] = max(f[3][25], f[3][25-10] + 25) = max(31,56)=56;
这才是正解（为什么会这样的原因，相信读者能自己分析出来）
有没有发现，只有最后一行代码才有用，这时我们想到了用一维数组来优化。

先写出状态转移方程f[j] = max(f[j], f[j – c[i]] + v[i])

我们可以继续分析一波数据
还是用上面的例子：
物品： a b c
体积： 5 4 6
价值; 10 7 14

当 i = 1 时
f[0] 到 f[4]显然都是零
f[5] = max(f[5], f[0] + 10)= 10
f[6] = max(f[6], f[1] + 10) = 10
…
f[9] = max(f[9], f[4] + 10) = 10
f[10] = max(f[10], f[5] + 10)=20
!!! 问题出现了，如果每件物品只拿一次，价值不可能出现20
仔细分析发现原来是物品a拿了两次既f[10]不仅由f[5]决定了而且还被f[0]影响了，这显然是不对的，这就是我们后面要讲的完全背包问题。
我们想出了一个解决办法，不是f[10]被前面多次刷新嘛，我们第二层循环倒着来。J=14开始（我们不分析这么多了背包就取14）到j>=c[i]就可以了，因为前面都是0，没有意义。
i = 1时
f[14] = max(f[14], f[9] + 10) = 10
f[13] = max(f[13], f[8] + 10) = 10
…
f[5] = max(f[5], f[0] + 10) = 10
i = 2时
f[14] = max(f[14], f[10] + 7) = 17
…
f[9] = max(f[9], f[5] + 7) = 17
f[8] = max(f[8], f[4] + 7) = 10;
看到没，f[9]到f[14]的值刷新了
i = 3 时
f[14] = max(f[14, f[8] + 14] = 24
f[13] = max(f[13], f[7] +14) = 24
…
后面就不列举了，我们要的结果f[14]已经出来了显然这是正确的答案。
由此可见对于二维数组，我们可以用一维滚动数组来实现，减少不必要的浪费。
重点来了！！！用滚动数组的时候内层循环一定要逆序

再写一点关于初始化的问题，对于背包问题，有要求背包装满与不装满两种情况

1. 装满那就要f[0] = 0; 其他的都为-∞，为什么呢，因为只有在背包容量为0的时候才可以一个都不装价值为0，当背包有容量，就可能装得下东西，但你不能选择什么都不装对吧，这不符合要求，所以初始化为-∞之后，只有当你装之后这个值才有意义。
2. 不要求装满就全部初始化为0，理由同上，装与不装是你的选择，你可以留着容量不装，这时所有值都有意义。
   最后贴上01背包的代码
   二维：

for(int i = 1; i <= N; i++)//N表示种类for(int j = 1; j <= V; j++)//V表示背包容量 这里循环正序逆序都行 if(j >= c[i])f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + v[i]) elsef[i][j] = f[i-1][j]cout << f[N][V];

滚动数组：

for(int i = 1; i <= N; i++)for(int j = V; j >= c[i]; j--)// 一定要逆序 f[j] = max(f[j], f[j - c[i]] + v[i]);cout << f[V];

注：此文章问原创，开源，可转载但请注明出处！