• Home
  • home > theory > algorithm > leetcode >

    DP笔记(9)：完全/多重/分组背包问题分析与总结

    Author：zhoulujun Date：

    几乎所有的「背包问题」都是基于「01 背包」演变而来！完全背包、多重背包、分组背包都可以由0-1背包去推导，本文讲解这三种的背包的解法。

    在《DP笔记(8)：动态规划背包相关问题学习总结——从01背包开始》中：

    根据物品限制条件的不同，背包问题可分为：

    • 0-1背包问题：每种物品只能选一次，典型问题是旅行者选择物品。

    • 完全背包问题：每种物品可以选无限次，典型问题是商品购买。

    • 多重背包问题：每种物品有数量限制，典型问题是资源分配。

    • 分组背包问题：物品分组，每组最多选一个，典型问题是课程教材选择。

    关于这几种常见的背包，其关系如下：

    几乎所有的「背包问题」都是基于「01 背包」演变而来，当我们确定一个问题是背包问题之后，可以根据其物品的「数量限制」来判别是何种背包问题，然后套用「01 背包」的思路来求解。

    完全背包问题

    有 n 种物品和一个最多能装重量为 W 的背包，第 i 种物品的重量为 weight[i]，价值为 value[i]，每种物品数量没有限制。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

    完全背包问题

    完全背包问题基本思路

    完全背包问题的特点：每种物品有无限件。

    我们可以参考「0-1 背包问题」的状态定义和基本思路，对于容量为 w 的背包，最多可以装w ÷ weight[i−1]件第 i−1 件物品。那么我们可以多加一层循环，枚举第 i−1 件物品可以选择的件数（0 ∼ w ÷weight[i−1]），从而将「完全背包问题」转换为「0-1 背包问题」。

    动态规划 + 二维基本思路

    定义状态

    定义状态 dp[i][w] 表示为：前 i 种物品放入一个最多能装重量为 w 的背包中，可以获得的最大价值。

    状态 dp[i][w] 是一个二维数组，其中第一维代表「当前正在考虑的物品种类」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。

    状态转移方程

    由于每种物品可选的数量没有限制，因此状态dp[i][w] 可能从以下方案中选择最大值：

    1. 选择 0 件第 i−1 件物品：可以获得的最大价值为 dp[i−1][w]

    2. 选择 1 件第i−1 件物品：可以获得的最大价值为 dp[i−1][w−weight[i−1]]+value[i−1]。

    3. 选择 22 件第 i−1 件物品：可以获得的最大价值为 dp[i−1][w−2×weight[i−1]]+2×value[i−1]。

    4. ……

    5. 选择k 件第 i−1 件物品：可以获得的最大价值为dp[i−1][w−k×weight[i−1]]+k×value[i−1]。

    注意：选择 k 件第 i−1 件物品的条件是 0≤k×weight[i−1]≤w。

    则状态转移方程为：

    dp[i][w]=max{dp[i−1][w−k×weight[i−1]]+k×value[i−1]}，0≤k×weight[i−1]≤w。

    dp数组初始化

    • 如果背包载重上限为 0，则无论选取什么物品，可以获得的最大价值一定是 0，即 dp[i][0]=0,0≤i≤size。

    • 无论背包载重上限是多少，前 0 种物品所能获得的最大价值一定为 0，即 dp[0][w]=0,0≤w≤W。

    最终代码
    function completePackMethod1(weight, value, W) { // 思路 1：动态规划 + 二维基本思路
  const size = weight.length;
  const dp = Array.from({ length: size + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= size; i++) { // 枚举前 i 种物品
    for (let w = 0; w <= W; w++) {// 枚举背包装载重量
      for (let k = 0; k <= Math.floor(w / weight[i - 1]); k++) {// 枚举第 i - 1 种物品能取个数
        // dp[i][w] 取所有 dp[i - 1][w - k * weight[i - 1] + k * value[i - 1] 中最大值
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - k * weight[i - 1]] + k * value[i - 1]);
      }
    }
  }
  return dp[size][W];
}


    复杂度分析

    image.png

    完全背包问题状态转移方程优化

    上之前的思路中，对于每种物品而言，每次我们都需要枚举所有可行的物品数目 k，这就大大增加了时间复杂度。

    实际上，我们可以对之前的状态转移方程进行一些优化，从而减少一下算法的时间复杂度。

    我们将之前的状态转移方程

    image.png

    通过观察可以发现：

    (1) 式中共有 k+1 项，(2) 式中共有 k 项；

    (2) 式整个式子与 (1) 式第 1∼k+1 项刚好相差一个 value[i−1]。

    则我们将 (2) 式加上value[i−1]，再代入(1) 式中，可得到简化后的「状态转移方程」为：

    image.png

    简化后的「状态转移方程」去除了对物品件数的依赖，也就不需要遍历 k 了，三层循环降为了两层循环。

    则状态转移方程为：

    image.png

    从上述状态转移方程我们可以看出：该式子与 0-1 背包问题中「思路 1」的状态转移式极其相似。

    唯一区别点在于：

    1. 0-1 背包问题中状态为 dp[i−1][w−weight[i−1]]+value[i−1]，这是第i−1 阶段上的状态值。

    2. 完全背包问题中状态为 dp[i][w−weight[i−1]]+value[i−1]，这是第 i 阶段上的状态值。


    动态规划 + 状态转移方程优化

    按照物品种类的序号、当前背包的载重上限进行阶段划分。

    定义状态

    定义状态 dp[i][w] 表示为：前i 种物品放入一个最多能装重量为 w 的背包中，可以获得的最大价值。

    状态dp[i][w] 是一个二维数组，其中第一维代表「当前正在考虑的物品种类」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。

    状态转移方程

    image.png

    初始条件

    • 如果背包载重上限为 0，则无论选取什么物品，可以获得的最大价值一定是 0，即dp[i][0]=0,0≤i≤size。

    • 无论背包载重上限是多少，前 0 种物品所能获得的最大价值一定为 0，即 dp[0][w]=0,0≤w≤W。

    最终代码

    根据我们之前定义的状态，dp[i][w] 表示为：前 i 种物品放入一个最多能装重量为 w 的背包中，可以获得的最大价值。则最终结果为 dp[size][W]，其中 size 为物品的种类数，W 为背包的载重上限。

    function completePackMethod2(weight, value, W) {// 思路 2：动态规划 + 状态转移方程优化
  const size = weight.length;
  const dp = Array.from({ length: size + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= size; i++) {// 枚举前 i 种物品
    for (let w = 0; w <= W; w++) { // 枚举背包装载重量
      if (w < weight[i - 1]) { // 第 i - 1 件物品装不下
        // dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
        dp[i][w] = dp[i - 1][w];
      } else {
        // dp[i][w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」与「前 i 种物品装入载重为 w - weight[i - 1] 的背包中，再装入 1 件第 i - 1 种物品所得的最大价值」两者中的最大值
        dp[i][w] = Math.max(dp[i - 1][w], dp[i][w - weight[i - 1]] + value[i - 1]);
      }
    }
  }
  return dp[size][W];
}



    完全背包问题滚动数组优化

    通过观察「思路 2」中的状态转移方程

    image.png

    可以看出：我们只用到了当前行（第i 行）的 dp[i][w]、dp[i][w−weight[i−1]]，以及上一行（第 i−1 行）的dp[i−1][w]。

    所以我们没必要保存所有阶段的状态，只需要使用一个一维数组dp[w] 保存上一阶段的所有状态，采用使用「滚动数组」的方式对空间进行优化（去掉动态规划状态的第一维）。

    动态规划 + 滚动数组优化


    定义状态

    定义状态 dp[w] 表示为：将物品装入最多能装重量为 w 的背包中，可以获得的最大价值。

    状态转移方程

    image.png

    注意：这里的 dp[w−weight[i−1]] 是第 i 轮计算之后的「第 i 阶段的状态值」。

    因为在计算 dp[w] 时，我们需要用到第 i 轮计算之后的 dp[w−weight[i−1]]，所以我们需要按照「从 0∼W 正序递推的方式」递推 dp[w]，这样才能得到正确的结果。

    因为 w<weight[i−1] 时，dp[w] 只能取上一阶段的 dp[w]，其值相当于没有变化，这部分可以不做处理。所以我们在正序递推 dp[w] 时，只需从 weight[i−1] 开始遍历即可。

    初始条件

    无论背包载重上限为多少，只要不选择物品，可以获得的最大价值一定是 

    0，即 dp[w]=0,0≤w≤W。

    最终结果

    根据我们之前定义的状态， dp[w] 表示为：将物品装入最多能装重量为 w 的背包中，可以获得的最大价值。则最终结果为 dp[W]，其中 W 为背包的载重上限。

    function completePackMethod3(weight, value, W) {
  const size = weight.length,dp = Array(W + 1).fill(0);
  for (let i = 1; i <= size; i++) { // 枚举前 i 种物品
    for (let w = weight[i - 1]; w <= W; w++) {   // 正序枚举背包装载重量
      // dp[w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」
      // 与「前 i 种物品装入载重为 w - weight[i - 1] 的背包中， 再装入 1 件第 i - 1 种物品所得的最大价值」两者中的最大值
      dp[w] = Math.max(dp[w], dp[w - weight[i - 1]] + value[i - 1]);
    }
  }
  return dp[W];
}

    如果面试官 要求先用二维dp数组实现，然后再用一维dp数组实现，最后再问，两个for循环的先后是否可以颠倒？为什么？

    完全背包问题的案例

    疯狂的采药

    萧炎是个天资聪颖的孩子，他想是成为世界上最伟大的药师！腰尘为了判断他的资质，给他出了一个难题。

    把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”



    多重背包问题

    多重背包问题：有 n 种物品和一个最多能装重量为 W 的背包，第 i 种物品的重量为 weight[i]，价值为 value[i]，件数为 count[i]。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

    多重背包问题

    多重背包问题基本思路

    我们可以参考「0-1 背包问题」的状态定义和基本思路，对于容量为 w 的背包，最多可以装分组背包问题公式件第 i−1 件物品。那么我们可以多加一层循环，枚举第 i−1 件物品可以选择的件数分组背包问题，从而将「完全背包问题」转换为「0-1 背包问题」。

    动态规划 + 二维基本思路

    按照物品种类的序号、当前背包的载重上限进行阶段划分。

    定义状态

    定义状态 dp[i][w] 表示为：前 i 种物品放入一个最多能装重量为 w 的背包中，可以获得的最大价值。状态dp[i][w] 是一个二维数组，其中第一维代表「当前正在考虑的物品种类」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。

    状态转移方程

    image.png

    如果背包载重上限为 0，则无论选取什么物品，可以获得的最大价值一定是 0，即 dp[i][0]=0,0≤i≤size。

    无论背包载重上限是多少，前 0 种物品所能获得的最大价值一定为 0，即 dp[0][w]=0,0≤w≤W。

    最终代码

    根据我们之前定义的状态，dp[i][w] 表示为：前 i 种物品放入一个最多能装重量为 w 的背包中，可以获得的最大价值。则最终结果为 dp[size][W]，其中 size 为物品的种类数，W 为背包的载重上限。

    function multiplePackMethod1(weight, value, count, W) {// 思路 1：动态规划 + 二维基本思路
  const size = weight.length;
  const dp = Array.from({ length: size + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= size; i++) {// 枚举前 i 种物品
    for (let w = 0; w <= W; w++) {// 枚举背包装载重量
      // 枚举第 i - 1 种物品能取个数
      for (let k = 0; k <= Math.min(count[i - 1], Math.floor(w / weight[i - 1])); k++) {
        // dp[i][w] 取所有 dp[i - 1][w - k * weight[i - 1]] + k * value[i - 1] 中最大值
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - k * weight[i - 1]] + k * value[i - 1]);
      }
    }
  }
  return dp[size][W];
}


    多重背包问题滚动数组优化

    在「完全背包问题」中，我们通过优化「状态转移方程」的方式，成功去除了对物品件数 k 的依赖，从而将时间复杂度下降了一个维度。

    而在「多重背包问题」中，我们在递推 dp[i][w] 时，是无法从 dp[i][w−weight[i−1]] 状态得知目前究竟已经使用了多个件第 i−1 种物品，也就无法判断第 i−1 种物品是否还有剩余数量可选。这就导致了我们无法通过优化「状态转移方程」的方式将「多重背包问题」的时间复杂度降低。

    但是我们可以参考「完全背包问题」+「滚动数组优化」的方式，将算法的空间复杂度下降一个维度。

    动态规划 + 滚动数组优化

    按照当前背包的载重上限进行阶段划分。

    定义状态

    定义状态 dp[w] 表示为：将物品装入最多能装重量为 w 的背包中，可以获得的最大价值。

    状态转移方程

    image.png

    初始条件

    无论背包载重上限为多少，只要不选择物品，可以获得的最大价值一定是 0，即 dp[w]=0,0≤w≤W。

    最终代码

    根据我们之前定义的状态， dp[w] 表示为：将物品装入最多能装重量为 w 的背包中，可以获得的最大价值。则最终结果为 dp[W]，其中 W 为背包的载重上限。

    function multiplePackMethod2(weight, value, count, W) { // 思路 2：动态规划 + 滚动数组优化
  const size = weight.length;
  const dp = new Array(W + 1).fill(0);
  for (let i = 1; i <= size; i++) {// 枚举前 i 种物品
    // 逆序枚举背包装载重量（避免状态值错误）
    for (let w = W; w >= weight[i - 1]; w--) { // 枚举第 i - 1 种物品能取个数
      for (let k = 0; k <= Math.min(count[i - 1], Math.floor(w / weight[i - 1])); k++) {
        // dp[w] 取所有 dp[w - k * weight[i - 1]] + k * value[i - 1] 中最大值
        dp[w] = Math.max(dp[w], dp[w - k * weight[i - 1]] + k * value[i - 1]);
      }
    }
  }
  return dp[W];
}


    混合背包问题

    混合背包问题：有 n 种物品和一个最多能装重量为 W 的背包，第 i 种物品的重量为weight[i]，价值为 value[i]，件数为 count[i]。其中：

    1. 当 count[i]=−1 时，代表该物品只有 1 件。

    2. 当count[i]=0 时，代表该物品有无限件。

    3. 当 count[i]>0 时，代表该物品有 count[i] 件。

    请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

    混合背包问题

    混合背包问题基本思路

    混合背包问题其实就是将「0-1 背包问题」、「完全背包问题」和「多重背包问题」这3 种背包问题综合起来，有的是能取 1 件，有的能取无数件，有的只能取 count[i] 件。

    其实只要理解了之前讲解的这 3 种背包问题的核心思想，只要将其合并在一起就可以了。

    混合背包问题就是把完全背包、01背包、多重背包

    并且在「多重背包问题」中，我们曾经使用「二进制优化」的方式，将「多重背包问题」转换为「0-1 背包问题」，那么在解决「混合背包问题」时，我们也可以先将「多重背包问题」转换为「0-1 背包问题」，然后直接再区分是「0-1 背包问题」还是「完全背包问题」就可以了

    function   mixedPackMethod1(weight, value, count, W) {
  const size = weight.length;
  const dp = Array.from({ length: size + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= size; i++) { // 枚举前 i 种物品
    for (let w = 0; w <= W; w++) { // 枚举背包装载重量
     
      if (count[i - 1] === -1) { // 如果是0-1背包问题
        if (w >= weight[i - 1]) {// 逆序枚举背包装载重量（避免状态值错误）
          dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]);
        } else {
          dp[i][w] = dp[i - 1][w];
        }
      }else if (count[i - 1] === 0) {// 如果是完全背包问题
        // 正序枚举背包装载重量
        dp[i][w] = dp[i - 1][w];
        if (w >= weight[i - 1]) { //请留意：动态规划 + 状态转移方程优化
          dp[i][w] = Math.max(dp[i][w], dp[i][w - weight[i - 1]] + value[i - 1]);
        }
      } else {// 如果是多重背包问题
        dp[i][w] = dp[i - 1][w];
        for (let k = 1; k <= count[i - 1] && k * weight[i - 1] <= w; k++) {
          dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - k * weight[i - 1]] + k * value[i - 1]);
        }
      }
    }
  }
  return dp[size][W];
}


    混合背包案例

    樱木花道后院里种了n棵樱花树，每棵都有美学值Ci。樱木花道在每天上学前都会来赏花。樱木花道可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看Ai遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间Ti 。樱木花道离去球场的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且樱木花道能准时参加篮球比赛？


    分组背包问题

    有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

    通俗的讲就是，给你N组（物品是分组的 ）物品，然后每一组你至多选择一个物品(也可以不选),每个物品都有自己的体积和价值，现在给你一个容里为M的背包，让你用这个背包装物品，使得物品价值总和最大。

    其实就类似于01背包，对于一个物品有两种决策选或不选，但是分组背包是在01背包的基础上对物品进行了分组，并且每一组只能最多选择一个物品。


    分组背包问题基本思路

    这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。

    对于第 i 组中的每个物品 (weight[k], value[k])，我们有两种选择：

    1. 如果选择该物品，并且其重量不超过 j，则背包的剩余容量为 j - weight[k]，前 i-1 组物品在剩余容量下的最大价值为 dp[i-1][j-weight[k]]，因此当前选择的总价值为 dp[i-1][j-weight[k]] + value[k]。

    2. 如果不选择该物品，则最大价值与前一组相同，即dp[i][j] = dp[i-1][j]。

    我们需要取这两种选择中的较大值，即 dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[k]] + value[k])。因此：

    • 状态定义：dp[i][j] 表示前 i 组物品中，背包容量为 j 时的最大价值。

    • 初始化状态：dp[0][j] = 0，表示没有任何物品时，背包容量为 j 的最大价值为 0。

    • 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[k]] + value[k])

    伪代码如下：

    for (所有的组k)
  for (枚举背包装载重量)
    for (遍历第 i 组的所有物品  )
      dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight] + value); // 更新最大价值

    尝试一下例题：

    一天，小 A 去远游，他有一个容量为45背包，现有3种物品，大致可分为 2 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

    物品重量价值属于第几组
    a10101
    b1051
    C504002


    最终代码

    function groupKnapsack(groups, capacity) {
  const n = groups.length; // 组数  
  const dp = new Array(n + 1).fill(null).map(() => new Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++) { // 枚举前 i 组物品
    for (let j = 0; j <= capacity; j++) { // 枚举背包装载重量
      dp[i][j] = dp[i - 1][j]; // 初始化为不选择第 i 组的任何物品  
      for (const [weight, value] of groups[i - 1]) { // 遍历第 i 组的所有物品  
        if (weight <= j) { // 如果物品重量不超过背包容量,当前物品可以放入背包
          dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight] + value); // 更新最大价值  
        }
      }
    }
  }
  return dp[n][capacity]; // 返回背包容量为 capacity 时的最大价值  
}




    参考文章：

    https://algo.itcharge.cn/10.Dynamic-Programming/04.Knapsack-Problem/02.Knapsack-Problem-02/

    https://programmercarl.com/背包问题理论基础完全背包.html

    一次性讲透背包问题：动态规划的深入解析与应用

    动态规划-混合、二维费用、分组背包 https://www.jianshu.com/p/91b30e49a9ec

    【算法】动态规划+“背包九讲”原理超详细讲解+常见dp问题（9种）总结目录 https://www.nowcoder.com/discuss/353147988501536768#P1048_01_163




    转载本站文章《DP笔记(9)：完全/多重/分组背包问题分析与总结》,
    请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9123.html

    收藏
    上一篇：DP笔记(8)：动态规划背包相关问题学习总结——从01背包开始
    下一篇：DP笔记(10)：背包相关问题，零钱兑换
    延伸阅读：