动态规划模型：0-1背包问题

2022-12-21 19:54:23 浏览数 (1)

大家好，我是前端西瓜哥。

本文为动态规划模型中，0-1背包问题的套路总结。

本文要求读者有一定的动态规划基础，知道状态转移方程、状态转移表等概念，能做一些简单的动态规划题解。

0-1背包问题

将 n 个物品（重量用 weight 数组表示）装入背包，在不超出背包总重量 w 的情况下，……

0-1 背包问题，就是依次决策是否将一个个物品装入背包中，

经典的 0-1背包问题还引入了价值维度，我将这种题型归为 二维费用的背包问题，会另外写一篇文章。这里只考虑重量维度。

0-1背包问题的求最大重量

将 n 个物品（重量用 weight 数组表示）装入背包，在不超出背包总重量 w 的情况下，求能装入的最大重量。

最值问题需要定义一个 boolean 类型的二维数组 dp[i][j]。

  1. i 表示在第几次决策，即是否装入 weight[i]，i 的范围为 [0, weight.length - 1]；
  2. j 表示到达的重量，范围为 [0, w]；
  3. 它的值，true 表示可达，false 表示不可达。

比如 dp[2][8] 为 true，表示在第 2 次决策后，背包的重量可以到达 8。

状态转移方程为：

代码语言：javascript复制
// 最新状态 = Max(不装入第 i 个物品, 装入)
dp[i][j] = dp[i-1][j] || dp[j - weight[i]];

记得处理数组索引值越界的情况。

TypeScript 代码实现：

代码语言：javascript复制
// 将 n 个物品（重量用 weight 数组表示）装入背包，在不超出背包总重量 w 的情况下，求能装入的最大重量
function knapsackMaxWeight(weight: number[], w: number) {
  const n = weight.length;
  // 初始化 boolean 类型的二维数组，范围：[n][w   1]
  const dp: boolean[][] = new Array(n);
  for (let i = 0; i < n; i  ) {
    dp[i] = new Array(w   1);
  }
  // 第 0 次决策的状态先初始化好，这样才能递推
  dp[0][0] = true; // 不装入
  if (weight[0] <= w) { // 装入 weight[0]，当然不能越界。
    dp[0][weight[0]] = true;
  }

  for (let i = 1; i < n; i  ) {
    for (let j = 0; j <= w; j  ) {
      if (
        dp[i - 1][j] === true ||
        (j - weight[i] >= 0 && dp[i - 1][j - weight[i]] === true)
      ) {
        dp[i][j] = true;
      }
    }
  }

  for (let i = w; i >= 0; i--) {
    if (dp[n - 1][i] === true) return i;
  }
  return 0;
}

0-1背包问题的求可行性

将 n 个物品（重量用 weight 数组表示）装入背包，背包容量为 w，能否刚好装满背包？

其实和上面的 “0-1背包问题的求最大重量” 基本一样，只是返回值不同，不再需要从后往前遍历找，而是直接返回最后一个元素的值 dp[n - 1][w]。

状态转移方程也和上面相同：

代码语言：javascript复制
// 最新状态 = Max(不装入第 i 个物品, 装入)
dp[i][j] = dp[i-1][j] || dp[j - weight[i]];

代码实现：

代码语言：javascript复制
// 将 n 个物品（重量用 weight 数组表示）装入背包，背包容量为 w，能否刚好装满背包？
function knapsackJustFillUp(weight: number[], w: number) {
  const n = weight.length;
  // 初始化 boolean 类型的二维数组，范围：[n][w   1]
  const dp: boolean[][] = new Array(n);
  for (let i = 0; i < n; i  ) {
    dp[i] = new Array(w   1).fill(false);
  }
  // 第 0 次决策的状态先初始化好，这样才能递推
  dp[0][0] = true; // 不装入
  if (weight[0] <= w) { // 装入 weight[0]，当然不能越界。
    dp[0][weight[0]] = true;
  }

  for (let i = 1; i < n; i  ) {
    for (let j = 0; j <= w; j  ) {
      if (
        dp[i - 1][j] === true ||
        (j - weight[i] >= 0 && dp[i - 1][j - weight[i]] === true)
      ) {
        dp[i][j] = true;
      }
    }
  }

  return dp[n - 1][w];
}

可以考虑在状态转移过程时，发现 dp[i][w] 变成 true 的时候，就直接直接返回 true，提前结束遍历。

相关 LeetCode 题：

  • 416、分割等和子集

0-1背包问题的求装满背包最少物品数

将 n 个物品（重量用 weight 数组表示）装入背包，背包容量为 w，求刚好装满背包的最少物品数。

涉及到数量，需要定义 number 类型的二维数组。

dp[i][j] 表示在决策第 i 个物品阶段，背包重量为 j 的情况下，装入的最少物品数量。比如 dp[2][6] 的值为 1，表示决策了第 2 个物体后，重量为 6，装入的最少物品数量为 1。

状态转移方程为：

代码语言：javascript复制
// 最新状态       不装入当前物品       装入当前物品（需要加一）
dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-weight[i]]   1);

代码实现：

代码语言：javascript复制
function knapsackMinCount(weight: number[], w: number): number {
  const n = weight.length;
  // 初始化 number 类型的二维数组，范围：[n][w   1]
  const dp: number[][] = new Array(n);
  for (let i = 0; i < n; i  ) {
    dp[i] = new Array(w   1).fill(Number.MAX_SAFE_INTEGER);
  }
  // 第 0 次决策的状态先初始化好，这样才能递推
  dp[0][0] = 0; // 不装入
  if (weight[0] <= w) { // 装入 weight[0]，当然不能越界。
    dp[0][weight[0]] = 1; // 装入第一个
  }

  for (let i = 1; i < n; i  ) {
    for (let j = 0; j <= w; j  ) {
      dp[i][j] = dp[i - 1][j]; // 不装入
      if (j - weight[i] >= 0 && dp[i - 1][j - weight[i]] !== Number.MAX_SAFE_INTEGER) {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - weight[i]]   1); // 装入
      }
    }
  }

  if (dp[n - 1][w] === Number.MAX_SAFE_INTEGER) return -1;
  return dp[n - 1][w];
}

通常我们会给 dp 初始化为最大数字，所以要注意 dp[i-1][j-weight[i]] 1 可能导致数值范围越界的情况。

0-1背包问题的求所有装法

定义 number 类型的二维数组。

dp[i][j] 表示决策第 i 个物品后，总重量为 j 的所有装法数量。

动态转移方程：

代码语言：javascript复制
//          不装入             装入
dp[i][j] = dp[i-1][j-1]   dp[i-1][j-weight[i]];

代码实现：

代码语言：javascript复制
function knapsackWays(weight: number[], w: number): number {
  const n = weight.length;
  // 初始化 number 类型的二维数组，范围：[n][w   1]
  const dp: number[][] = new Array(n);
  for (let i = 0; i < n; i  ) {
    dp[i] = new Array(w   1).fill(0);
  }
  // 第 0 次决策的状态先初始化好，这样才能递推
  dp[0][0] = 1; // 不装入
  if (weight[0] <= w) { // 装入 weight[0]，当然不能越界。
    dp[0][weight[0]] = 1; // 装入第一个
  }

  for (let i = 1; i < n; i  ) {
    for (let j = 0; j <= w; j  ) {
      dp[i][j] = dp[i - 1][j];
      if (j - weight[i] >= 0) {
        dp[i][j]  = dp[i - 1][j - weight[i]];
      }
    }
  }

  return dp[n - 1][w];
}

一个容易纠结的点是 dp[0][0] 的初始值应该是 0 还是 1。答案是初始化为 1，因为不装入也是一种选择。

相关 LeetCode 题：

  • 494、目标和

GitHub 项目

以上实现我已经放到 GitHub 上了，并写了一些测试用例，可通过 npx jest 做测试。

https://github.com/F-star/dynamic-programming-play/blob/master/src/knapsack/knapsack_01/knapsack_01.ts

不保证一定正确，欢迎提供你的测试用例。

结尾

总结一下，0-1背包问题常见有 4 种：求能装入的最大重量、求能否刚好装满、求刚好装满的最少物品数、求刚好装满的所有数量，希望你能好好掌握。

我是前端西瓜哥，欢迎关注我，学习更多前端知识。

网站 github 编程算法 git 开源

0 人点赞