「这是我参与2022首次更文挑战的第1天，活动详情查看：2022首次更文挑战」
前言
动态规划和递归是一对CP，递归通过将大问题分解成小问题以求得答案，而动态规划则是通过求解小问题来组成大问题的解。虽然其本质都是先求小问题的解，但是问题的推算不同：
- 递归：大问题 -> 小问题
- 动态规划：小问题 -> 大问题
在平常的代码中，递归是比较符合我们思考的方向的。在编码中，我们经常自然而然的将复杂问题分解成简单问题并分步进行。但是如果要思考如何如何通过小问题来求解大问题，就需要比较强的推理能力了。其中推理的重点在于
- 定义dp数组（主要是dp下标及含义）
- 递推公式（小问题转化为大问题）
- dp初始化（已知小问题的解）
- dp遍历生成（逐步推导出答案）
其中的重中之重为递推公式
01背包解题步骤
背包问题是动态规划中比较常见的一种类型，今天我们来学习背包问题中的01背包。
Q：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
如果采用暴力解法的话，我们需要考虑每件物品取/不取的情况，其算法复杂度为O(2^N)。我们可以通过动态规划来使其降低为O(WN)。
1.定义dp数组
我们要求的是在总容量为W，物品有N件的情况下，可以取得的最大价值Vmax。有两个变量容量w及物品n，我们设要求的总价值dp[i][j]，其中i表示物品可取范围为前i件，即范围[0, i]，j表示背包容量。
2.递归公式
分两种情况
- 当我们不取第i件物品时
dp[i][j] = dp[i - 1][j] 复制代码
- 当我们取第i件物品时
dp[i][j] = dp[i - 1][j - w[i]] + v[i] 复制代码
所以可以得出递推公式
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) 复制代码
3.dp初始化
我们知道，在容量为0的时候时候，dp[i][j]肯定为0
dp[i][0] = 0 复制代码
当所选的物品为0的时候，价值也为0
dp[0][j] = 0 复制代码
4.dp遍历生成
for (let i = 1; i <= N; i++) { for (let j = 1; j <= W; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) } } 复制代码
01背包实例
Q：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
N = 5; W = 20; w = [4, 5, 10, 11, 13]; v = [3, 4, 7, 8, 9]; 复制代码
function knapsack() { const N = 5; const W = 43; const w = [4, 5, 10, 11, 13]; const v = [3, 4, 7, 8, 9]; // 1.定义dp数组 // dp[n][w]表示容量为w的情况下可取前n件物品时的最大价值 const dp = [] // 2.初始化dp数组 // 容量为0时价值为0 for (let i = 0; i <= N; i++) { dp[i] = [] dp[i][0] = 0 } // 可取物品为0时价值为0 for (let j = 0; j <= W; j++) { dp[0][j] = 0 } // 4.dp遍历生成 // 我们第一层遍历物品 for (let i = 1; i <= N; i++) { // 第二层遍历容量 for (let j = 1; j <= W; j++) { // 3.推导公式 // 在本例子中要注意dp[i][j]对应的是可取第i个物品的最大价值 // 但是第i个物品的重量和价值对应的是w[i - 1]和v[i - 1] if (j >= w[i - 1]) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]) } else { dp[i][j] = dp[i - 1][j] } } } return dp[N][W] } 复制代码
因为我设置的容量刚刚好是所有物品的重量之和，所以得出的结果为所有物品价值之和。
动态规划的解答实际是个填表的过程，如果能做出来就能通过DP查看到不同变量下不同的解，会发现挺有意思的。(PS：推不出递归公式的时候实际想哭！)
更改遍历顺序
刚才我们在遍历生成dp数组的时候，是先遍历物品再变量容量的，那么调换下顺序是否可行呢？
// ... // 先遍历容量 for (let j = 1; j <= W; j++) { // 再遍历物品 for (let i = 1; i <= N; i++) { if (j >= w[i - 1]) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]) } else { dp[i][j] = dp[i - 1][j] } } } // ... 复制代码
可以发现，其实答案是一样的，它们的区别只在于填表的顺序不同。方案一是先从左到右，方案二是先从上到下。
最佳方案
我们之前求的是最大价值，但是如果要输出最大价值的方案呢
function knapsack() { const N = 5; const W = 29; const w = [4, 5, 10, 11, 13]; const v = [3, 4, 7, 8, 9]; const dp = [] // 使用trace变量来记录选择 const trace = [] for (let i = 0; i <= N; i++) { // 初始化二维trace trace[i] = [] dp[i] = [] dp[i][0] = 0 } for (let j = 0; j <= W; j++) { dp[0][j] = 0 } for (let i = 1; i <= N; i++) { for (let j = 1; j <= W; j++) { if (j >= w[i - 1]) { // 不同之处主要是在这里要记录trace // trace[i][j] === 1 表示当前最大价值方案选取了第i件物品 if (dp[i - 1][j] >= dp[i - 1][j - w[i - 1]] + v[i - 1]) { trace[i][j] = 0 } else { trace[i][j] = 1 } dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]) } else { dp[i][j] = dp[i - 1][j] trace[i][j] = 0 } } } // 通过trace推出选取的物品 const ans = [] let rest = W let i = N while(i > 0) { if (trace[i][rest] === 1) { rest -= w[i - 1] ans.push(i) } i-- } return ans } 复制代码
结语
动态规划中的01背包是非常经典的题型，大家好好理解学习一定可以掌握的。
