「这是我参与2022首次更文挑战的第2天，活动详情查看：2022首次更文挑战」
前言
我们上篇文章学习了动态规划01背包的问题，本篇文章我们继续学习完全背包。大家可以在学习完01背包的基础上再进行学习，比较其两者的解题差异。
完全背包
完全背包实际由01背包演化而来，01背包中每个物品的个数都是1，而完全背包不限制物
品数量，每种物品的数量无限，可以重复加入背包中。
我们来看看完全背包的提问
Q：一共有N种物品，每种物品有无限多个，第i（i从1开始）种物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
解题步骤
我们说的解题步骤实际上是动态规划的一个解题步骤
1.定义dp数组
dp数组的定义实际和01背包相同
我们要求的是在总容量为W，物品有N件的情况下，可以取得的最大价值Vmax。有两个变量容量w及物品n，我们设要求的总价值dp[i][j]，其中i表示物品可取范围为前i件，即范围[0, i]，j表示背包容量。
dp[i][j] // i表示物品可取范围为前i件 j表示背包容量 复制代码
2.递归公式
完全背包和01背包的差异主要体现在递推公式
依据题目，我们可以重复放入第i件物品，所以我们的最大价值应该对比放入不同件数的最大价值
dp[i][j] = Math.max(dp[i - 1][j - n * w[i]] + n * v[i]) // 0 =< n <= j / w[i] n为整数 复制代码
有两种不同的递推思路，其中一种不好理解，我也没理解过来，所以就只列出了第二种
3.dp初始化
初始化和01数组相同
在容量为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++) { for (let n = 0; n <= parseInt(j / w[i])) { dp[i][j] = Math.max(dp[i][j] || 0, dp[i - 1][j - n * w[i]] + n * v[i]) } } } 复制代码
完全背包实例
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] for (let n = 0; n <= parseInt(j / w[i - 1]); n++) { dp[i][j] = Math.max(dp[i][j] || 0, dp[i - 1][j - n * w[i - 1]] + n * v[i - 1]) } } } return dp[N][W] } 复制代码
多重背包
我们在完全背包的基础上再了解下多重背包
多重背包也是01背包的一种变形，其问题形式为
Q：一共有N种物品，第i（i从1开始）种物品的数量为K[i]，重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
可以发现多重背包和完全背包非常相似，主要区别在于物品数量限制。其解题思路和完全背包几乎一样，仅仅在递推公式有所区别
dp[i][j] = Math.max(dp[i - 1][j - n * w[i]] + n * v[i]) // (0 =< n <= j / w[i]) 且 (n <= k[i]) n为整数 复制代码
总结
动态规划的三种背包类型，01背包，多重背包，完全背包就已经结束了。后面我们将学习动态规划的另一类问题：公共子串。
