问题

n个物品，物品有价值和重量两个属性。

1个背包，背包容量w。

怎样组合物品，能使装入背包的物品价值最大？每种物品只有一个，装或者不装（1或者0，所以叫01背包问题）。

例子

n=3，w=4。物品列表如下：

解法

可以使用回溯法和动态规划求解，用动态规划最佳。

动态规划

五部曲

确定dp数组以及下标的含义

我们把n个物品从0到n-1进行编号，dp[i][j] 表示从下标为0到i的物品里任意组合，放入容量为j的背包，价值总和的最大值。j 是指背包的容量，它即不是背包的剩余容量，也不是背包里物品的总重量，它就是背包容量（好多资料对 j 的含义解释的不够清楚，导致很多人在理解状态转移方程时脑子转不过弯来）。有人会问，背包容量不是w吗，用二维数组的列表示背包容量，难道背包容量会变？别忘了，动态规划的核心思想就是之前做过的事可以为后面所做的事铺路，我考虑容量为0、1、2…的背包，就是为容量为w的背包铺路，我们最终关心的是容量为w的背包。

确定状态转移方程

我们约定，物品i的重量为w[i]，物品i的价值为v[i]。

假设我们已经知道了dp[i][j]，现在求dp[i + 1][j + w[i + 1]]，很显然，dp[i + 1][j + w[i + 1]] = dp[i][j] + v[i + 1]。

解释一下，当背包容量从j增加到j + w[i + 1]后，因为新增容量w[i + 1]刚好是物品i + 1的重量，所以能将物品i + 1放进背包里，那么现在的总价值等于原来的总价值加上物品i + 1的价值v[i + 1]。

上面是从前往后考虑问题，动态规划是从后往前考虑问题，如果我们要求的是dp[i][j]，那上述方程就变成了：

dp[i][j] = dp[i - 1][j - w[i]] + v[i]

假如物品i没法放进容量为j的背包里，那么：

dp[i][j] = dp[i - 1][j]

物品放进背包或不放进背包两种情况的价值取最大值（跟物品价值是否为负值无关，后面举例说明），那么：

dp[i][j] = Math.max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])

确定遍历顺序

在求解时，需要遍历物品和背包容量。按照物品编号从小到大和背包容量从小到大的方式遍历，伪代码如下：

for (int i = 1; i < n; i++) {for (int j = 1; j <= w; j++) {}
}

从1开始遍历，是为了防止越界。

dp数组如何初始化

只有确定了遍历顺序，才能明确dp数组该如何初始化。上面提到过动态规划的核心就是之前做过的事可以为后面所做的事铺路，那你起码得先给我铺一条路，我才能在这基础上继续干活吧。

当背包容量为0的时候，一个物品都装不进去，毫无疑问dp[i][0] = 0。

将物品0往各种容量的背包里放，能放进去，dp[0][j] = v[0]，放不进去，dp[0][j] = 0。

dp[i][0] 和 dp[0][j] 都已经初始化了，那么其他下标应该初始化多少呢？

dp[i][j]在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数，那么其他下标都初始化为0就可以了，因为0就是最小的了，不会影响取最大价值的结果。

如果题目给的价值有负数，那么其他下标就要初始化为负无穷了。例如：一个物品的价值是-2，但对应的位置依然初始化为0，那么取最大值的时候，就会取0而不是-2了，所以要初始化为负无穷。

而背包问题的物品价值都是正整数，所以初始化为0，就可以了。

初始化后的dp数组如下：

举例推导dp数组

举例推导一遍dp数组，看合不合理。

这里再贴一次物品列表，方便对比：

dp数组如下：

有了dp数组，就方便解释dp[i][j] = Math.max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])这行代码了。

当i = 2，j = 4时，dp[i - 1][j - w[i]] + v[i] = dp[1][0] + 30 = 0 + 30 = 30，此时背包只装物品2，显然背包价值没有同时装物品0和物品1高，而dp[i - 1][j] = dp[1][4] = 35就是同时装了物品0和物品1。

接上面，当i = 1，j = 4时，dp[i - 1][j - w[i]] + v[i] = dp[0][1] + 20 = 15 + 20 = 35，此时背包同时装了物品0和物品1，而dp[i - 1][j] = dp[0][4] = 15，背包里只装了物品0。

所以知道为啥要取更大的那个值了吧。

代码示例

public class KnapsackProblem01 {/*** 01背包问题求最大价值* @param goods 物品列表，二维数组中的一维数组用来存储物品信息，一维数组的0下标是重量，1下标是价值。* @param w 背包容量* @return 最大价值*/public static int maxValue(int[][] goods, int w) {int[][] dp = new int[goods.length][w + 1];// 初始化dp数组的第0列for (int i = 0; i < goods.length; i++) {dp[i][0] = 0;}// 初始化dp数组的第0行for (int j = 0; j <= w; j++) {if (j >= goods[0][0]) { // 背包容量能容纳物品0dp[0][j] = goods[0][1]; // 背包价值等于物品0的价值} else {dp[0][j] = 0;}}for (int i = 1; i < goods.length; i++) {for (int j = 1; j <= w; j++) {if (goods[i][0] <= j) { // 背包容量能容纳物品idp[i][j] = Math.max(dp[i - 1][j - goods[i][0]] + goods[i][1], dp[i - 1][j]); // 放或不放寻找最优} else {dp[i][j] = dp[i - 1][j];}}}return dp[goods.length - 1][w]; // 最终解就是背包容量为w，考虑所有物品}public static void testCase() {int[][] goods = {{1, 15}, {3, 20}, {4, 30}};System.out.println(maxValue(goods, 4));}public static void main(String[] args) {testCase();}}