动态规划-完全背包-阿里云开发者社区

动态规划-完全背包

2023-05-10 93

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 前言我们上篇文章学习了动态规划01背包的问题，本篇文章我们继续学习完全背包。大家可以在学习完01背包的基础上再进行学习，比较其两者的解题差异。

「这是我参与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])
    }
  }
}
复制代码

完全背包实例

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背包，多重背包，完全背包就已经结束了。后面我们将学习动态规划的另一类问题：公共子串。