经典动态规划：0-1 背包问题
问题引入
给定一个可装载容量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
样例：N = 3, W = 4; wt = [2, 1, 3]; val = [4, 2, 3]
int knapsack(int W, int N, int[] wt, int[] val);
问题分析
第一眼看到这个问题，首先想到直接用「回溯」暴力求解。这个问题其实和 排列/组合/子集 问题 中的子集问题很相似，下面给出回溯树：
其中「黄色」标识的分支为大于容量W的情况，「绿色」标识的分支为最优解
但是今天我们的主题是利用「动态规划」求解本问题，让我们来复习一下动态规划的思维框架：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义
明确「状态」和「选择」
我们先明确一下原问题「给定背包容量和可选物品，要求价值最大化」，描述这样一个原问题需要给出两个条件，即：「背包的容量」和「可选择的物品」
而「状态」是原问题和子问题中会发生变化的变量，所以「状态」有两个，即：「背包的容量」和「可选择的物品」
再来确定「选择」，「选择」是导致「状态」产生变化的行为。这不就是对于每个可选择的物品，选择「装进背包」或者「不装进背包」嘛！！！
明确了「状态」和「选择」，基本就可以开始套框架了
# 进行状态转移for 状态1 in 状态1的所有取值： for 状态2 in 状态2的所有取值： for ... dp[状态1][状态2][...] = 求最值(选择1，选择2...)明确dp数组的定义
由于「状态」有两个，所以需要一个二维的dp[][]数组。数组的下标就是状态转移中会变化的量，而数组的值就是子问题的最优解
故：dp[i][w]的定义如下：对于前i个物品，当前背包容量为w，这种情况下背包可以装下的最大价值就是dp[i][w]
例：如果dp[3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6
根据这个定义，原问题的最优解即为dp[N][W]
现在，我们也可以很快确定 base case。即：dp[0][...] = dp[...][0] = 0，因为没有物品或背包没有空间的时候，能装下的最大价值就是 0
所以细化上面的框架后即为：
int[][] dp[N+1][W+1]dp[0][...] = dp[...][0] = 0for i in [1...N]: for w in [1...W]: dp[i][w] = max( 把物品 i 装进背包, 不把物品 i 装进背包 )return dp[N][W]根据「选择」，思考状态转移的逻辑
简单说就是，上面伪码中「把物品i装进背包」和「不把物品i装进背包」怎么用代码体现出来呢？
这就要结合对dp数组的定义，看看这两种选择会对状态产生什么影响
注：这里的dp数组整体向后偏移了一位，即：dp[i][w]对应的是wt[i-1]和val[i-1]
如果不把物品i装进背包，显然最大价值dp[i][w]应该等于dp[i-1][w]，继承之前的结果
如果把物品i装进背包，那么dp[i][w]应该等于val[i-1] + dp[i-1][w - wt[i-1]]
如果选择将第i个物品装进背包，那么第i个物品的价值val[i-1]肯定就到手了，接下来就要在剩余容量w - wt[i-1]的限制下，在前i - 1个物品中挑选，求最大价值，即dp[i-1][w - wt[i-1]]
根据上面的分析，我们可以更近一步细化代码：
for i in [1...N]: for w in [1...W]: dp[i][w] = max( val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w] )return dp[N][W]代码实现
xxxxxxxxxxint knapsack(int W, int N, int[] wt, int[] val) { int[][] dp = new int[N + 1][W + 1]; for (int i = 1; i <= N; i++) { for (int w = 1; w <= W; w++) { // 这种情况无法装下第 i 个物品，只能选择不装入 if (w - wt[i - 1] < 0) dp[i][w] = dp[i - 1][w]; else { dp[i][w] = Math.max( dp[i - 1][w], // 不装入 val[i - 1] + dp[i - 1][w - wt[i - 1]] // 装入 ); } } } return dp[N][W];}空间优化
x
int knapsack(int W, int N, int[] wt, int[] val) { int[] dp = new int[W + 1]; for (int i = 1; i <= N; i++) { // 注意：需要反向遍历，不然会覆盖上一轮的结果 for (int w = W; w >= 0; w--) { // 这种情况无法装下第 i 个物品，只能选择不装入 if (w - wt[i - 1] < 0) dp[w] = dp[w]; else { dp[w] = Math.max( dp[w], // 不装入 val[i - 1] + dp[w - wt[i - 1]] // 装入 ); } } } return dp[W];}扩展
上面都是基于「背包至多能装多大价值的物品」分析的
下面还有另外一种情况「若背包恰好装满，求至多能装多大价值的物品」
dp[i][w]的定义如下：对于前i个物品，当前背包容量为w，这种情况下背包恰好装满的最大价值就是dp[i][w]
因此，base case 相应的也需要改变一下下
对于第一种情况的 base case，dp[0][...] = dp[...][0] = 0，因为没有物品或背包没有空间的时候，能装下的最大价值就是 0
而对于这种情况的 base case，dp[0][0] = 0，因为没有物品或背包没有空间的时候，能装下的最大价值就是 0；而dp[0][1...W] = Integer.MIN_VALUE，因为物品为 0 但空间不为 0 的时候，一定不能装满，所以都设置为最小值
至于其他的逻辑都一样，如果最终结果为负数，那么就不能恰好装满！！
xxxxxxxxxxint knapsack(int W, int N, int[] wt, int[] val) { int[][] dp = new int[N + 1][W + 1]; // base case for (int i = 1; i <= W; i++) dp[0][i] = Integer.MIN_VALUE; for (int i = 1; i <= N; i++) { for (int w = 1; w <= W; w++) { // 这种情况无法装下第 i 个物品，只能选择不装入 if (w - wt[i - 1] < 0) dp[i][w] = dp[i - 1][w]; else { dp[i][w] = Math.max( dp[i - 1][w], // 不装入 val[i - 1] + dp[i - 1][w - wt[i - 1]] // 装入 ); } } } return dp[N][W] < 0 ? 0 : dp[N][W];}空间优化
关于空间优化的技巧可见 动态规划之最长回文子序列「dp 空间优化」
int knapsack(int W, int N, int[] wt, int[] val) { int[] dp = new int[W + 1]; // base case for (int i = 1; i <= N; i++) dp[i] = Integer.MIN_VALUE; for (int i = 1; i <= N; i++) { // 注意：需要反向遍历，不然会覆盖上一轮的结果 for (int w = W; w >= 0; w--) { // 这种情况无法装下第 i 个物品，只能选择不装入 if (w - wt[i - 1] < 0) dp[w] = dp[w]; else { dp[w] = Math.max( dp[w], // 不装入 val[i - 1] + dp[w - wt[i - 1]] // 装入 ); } } } return dp[W] < 0 ? 0 : dp[W];}