我对背包问题理解
背包问题
背包问题是经典的考察动态规划应用的题目，对其加上不同的限制和条件，可以衍生出诸多变种，若要全面理解动态规划，掌握背包问题是必不可少的。由于本人水平有限，本文只是个人对背包问题的理解，如有不正确之处还请谅解和指正。
题目描述
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
所有背包问题的主干与题目描述中的一致，但是加上不同的条件限制后，会形成各种背包问题的变种。下文是作者对0-1背包和完全背包问题的理解笔记。为啥只有这两种，水平实在有限。
0-1背包问题
0-1背包问题是最基础的背包问题，顾名思义0-1背包即每种的物品仅有一件，那么对于指定的物品的选择只有取或者不取两种状态。现在我们定义一个状态F[i][v]用来表示可选择的物品范围为前i件物品并且所有物品的体积总和不超过v时，背包内所有物品的价值总和最大。那么，F[i][v]则可以通过以下两种状态转移得到：
- 如果不选第i件物品，那么最大价值总和为取前i-1件物品且背包容量不超过v时的最大价值，即
F[i][v] = F[i-1][v] - 如果选择第i件物品，那么最大价值总和为取前i-1件物品且背包容量不超过v-c[i]时的最大价值加上第i件物品的价值，即
F[i][v] = F[i-1][v-c[i]] + w[i]
但是从哪种状态转移过来的最大价值总更大呢，所以要对转移的状态进行比较，取更大的价值，因此得到状态转移方程如下：
F[i][v] = max{F[i-1][v], F[i-1][v-c[i]] + w[i]};
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。
现在，让我们来对所有的状态进行枚举，即通过遍历所有的物品和体积来找出最大价值总和，遍历顺序为第一层循环遍历所有的物品，第二层循环遍历背包容量，即考虑的是取或不取第i件物品对背包可用体积的影响，如下：
public int findMaxValue(int[] c, int[] w, int idx, int vol) {
int[][] dp = new int[idx + 1][vol + 1];
// i是从1开始，所以在cw数组取值时都要减一
for (int i = 1; i <= idx; i++) {
for (int v = 0; v <= vol; v++) {
dp[i][v] = dp[i - 1][v];
if (v >= c[i-1]) {
dp[i][v] = Math.max(dp[i][v], dp[i-1][v - c[i-1]] + w[i-1]);
}
}
}
return dp[idx][vol];
}
接下来对上述方法的两个方面进行说明：
-
为什么dp数组的长度为
idx+1和vol+1？因为动态规划问题中的边界条件对结果的影响很大，因此需要留出空间对边界值进行赋值，而在背包问题中，不同的边界值可以产生不同的结果，下文会进行介绍。
-
为什么最大值是
dp[idx][vol]而不是dp[idx][0...vol]中的最大值呢？实际上这与我们对边界值的初始化有关，当把
F[0][0...vol]都初始化为0时，所有F[i][v]中的值表示的是背包容量不超过v时的最大价值，即dp[idx][vol]可以由idx-1下体积不超过vol-w或vol时的最大价值转移而来；当把F[0][0]都初始化为0，而F[0][1...vol]都初始化为负无穷时，所有F[i][v]中的值表示的是背包容量恰好为v时的最大价值，即dp[idx][vol]只能由idx-1下体积恰好为vol-w或vol时的最大价值转移而来。我们也可以这样理解，如果要求背包恰好装满，那么没有物品可以选择的情况下（i=0时），只有体积为0是满足恰好装满的并且此时的最大价值为0（
F[0][0]=0），而其他体积是不可能达到的用负无穷表示（F[0][0...val]=-INF）；如果没有要求背包必须装满，那么没有物品可以选择的情况下，背包没有填满也是合法的且此时的最大价值为0（F[0][0...val]=0）。从数字层面来说，当i为1时，如果
dp[0][0...vol]为0，那么dp[1][0...vol]在背包体积v大于物品体积的情况下一定为w[i-1]（dp在未初始化时默认所有值都为0，取最大值后一定为w[i-1]）；如果dp[0][1...vol]为负无穷，那么在背包体积不恰好等于物品体积，即vol-c[i-1]不为0时dp[1][vol]为负无穷，所以在后续的状态转移过程中如果是从负无穷转移过来的，那么转移得到的状态也为负无穷。所以，在上述方法中我们将
dp[0][0...vol]隐式地初始化为了0，所以最终结果dp[idx][vol]就是最大价值；如果我们将dp[0][1...vol]为负无穷，那么最大值则在dp[idx][0...vol]之间，因为体积恰好装满时，价值不一定是最大的。
空间复杂度优化
从状态转移方程中可以看出，F[i][v]是由F[i-1][v]和F[i-1] [v-c[i]]两个子问题递推而来，即F[i][...]的值只与F[i-1][...]有关，因此我们可以进行空间压缩，只用一维数组来保存第i-1次循环的值。那如何保证在推在第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]]的值。代码如下：
public int findMaxValue(int[] c, int[] w, int idx, int vol) {
int[] dp = new int[vol + 1];
// i是从1开始，所以在cw数组取值时都要减一
for (int i = 1; i <= idx; i++) {
for (int v = vol; v >= c[i-1]; v--) {
dp[v] = Math.max(dp[v], dp[v - c[i-1]] + w[i-1]);
}
}
return dp[vol];
}
为什么以v=V..0的顺序推F[v]才能保证转移的状态的是正确的呢？需要注意到的是F[v]的状态转移是依赖于F[v-c[i]]的，从v...0的顺序遍历可以保证每次从F[v-c[i]]转移的值都是从i-1轮循环计算得到的（当某个v从i-1轮循环的v-c[i]转移得到F[v]后，F[v]则表示取了一件物品i的最大价值，由于v递减而c[i]为固定值，v-c[i]的值不可能比上个经过状态转移的v更大，所以v-c[i]只会取到上一轮[i-1轮]的值，不可能取到本轮[i轮]转移后的值），从逻辑意义上来说这样的循环顺序能够保证，到选择第i件物品时，能够进行转移的值都是不包含第i件物品的；如果遍历顺序为0...v则不能保证从v-c[i]得到的值都是从F[i-1]计算得到的，因为在v逐渐递增的过程中v-c[i]可能会等于之前已经转移过的某个v值，导致可转移的值可能已经包含了第i件物品，这与本题意不符，但它却是完全背包问题最简捷的解决方案，故学习只用一维数组解0-1背包问题是十分必要的。
总结
0-1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0-1背包问题求解。一定要明白基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。
完全背包问题
完全背包问题与0-1背包问题不同的地方在于，0-1背包每种物品只能选一次，你的选择只有选或者不选两者；而完全背包每种物品可以选无限次，但是选择的数量上限最多为v/c[i]。由此我们可以很容易的想到，在0-1背包的基础上再加一层循环来表示，选择第i件物品的个数，代码如下：
public int findMaxValue(int[] c, int[] w, int idx, int vol) {
int[][] dp = new int[idx + 1][vol + 1];
// i是从1开始，所以在cw数组取值时都要减一
for (int i = 1; i <= idx; i++) {
for (int v = 0; v <= vol; v++) {
for (int k = 0; k * c[i-1] <= v; k++) {
dp[i][v] = Math.max(dp[i][v], dp[i - 1][j - k * c[i-1]] + k * w[i-1]);
}
}
}
return dp[idx][vol];
}
该状态转移方程表示，在可选的物品为前i件且体积小于v时的最大价值，从数学意义上来讲就是在第三层循环时确定F[i][v]的最大价值：当k=0时，dp[i][v]等于d[i-1][v]，然后随着k不断增大，dp[i - 1][j - k * c[i]] + k * w[i]表示在未选择第i件物品的基础上分别选择0...v/c[i]件第i件物品的最大价值，并且每次都与dp[i][v]进行比较，从而确定dp[i][v]的最大价值。
这种方式因为有三层循环所以时间复杂度会比较高，所以我们换一种思考方式。0-1背包问题由于每件物品只能选择一次，所以在选择第i件物品时只能从第i-1件物品的状态下转移获得，但完全背包问题每件物品能选无限次，所以在体积为v的状态要考虑从可能选择了第i件物品的状态和未选第i件物品的状态进行转移。代码如下：
public int findMaxValue(int[] c, int[] w, int idx, int vol) {
int[][] dp = new int[idx + 1][vol + 1];
// i是从1开始，所以在cw数组取值时都要减一
for (int i = 1; i <= idx; i++) {
for (int v = 0; v <= vol; v++) {
dp[i][v] = dp[i-1][v];
if(v >= c[i-1]) {
dp[i][v] = Math.max(dp[i][v], dp[i][v - c[i-1]] + w[i-1]);
}
}
}
return dp[idx][vol];
}
空间复杂度优化
在介绍0-1背包问题时，阐述了为什么要按体积逆序遍历才能保证每件物品只能选择一次；同时也说明为什么体积正序遍历表示每件物品能选多次。所以完全背包问题的空间复杂度优化只要改变体积的遍历方向即可，代码如下：
public int findMaxValue(int[] c, int[] w, int idx, int vol) {
int[] dp = new int[vol + 1];
// i是从1开始，所以在cw数组取值时都要减一
for (int i = 1; i <= idx; i++) {
for (int v = c[i]; v <= vol; v++) {
dp[v] = Math.max(dp[v], dp[v - c[i-1]] + w[i-1]);
}
}
return dp[vol];
}
总结
如果能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。