01背包问题#

题目描述#

给定 n 个物品，第 i 个物品的重量为 wgt[i−1]、价值为 val[i−1] ，和一个容量为 cap 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。

举个例子：

假设背包容量 cap = 50，那么上表中最优的方案就是将香蕉和葡萄放入背包中，最大价值能够达到 270，共占用 50 的背包容量。

算法追踪#

接下来我们来看一个算法追踪，假设：

const wgt = [2, 3, 4, 5] // 物品重量
const val = [3, 4, 5, 6] // 物品价值
const cap = 5 // 背包容量

首先会构建一个二维数组作为我们的 dp 数组。整个二维数组为 dp[i][c]，也就是说，有多少个物品，这个二维数组就有多少行，背包容量有多大，这个二维数组就有多少列。另外会把物品0和容量0也算进去，因此整个二维数组行= 物品数+1，列=背包容量数+1. 二维数组里面的每一项对应当前物品以及容量所对应的最大价值。

1. 只考虑物品1（重量2，价值3）

   前两个为 0 ，因为容量不够，无法放下物品 1. 从容量 2 开始可以放下物品 1，因此最大价值为 3

   
   2. 考虑放入物品 2（重量为3，价值为4） - 容量2: 只能放下物品1，最大价值为3 - 容量3 和 容量 4：物品1和物品2都能放下，但是不能同时放下，只能放一个，选择物品2，因为物品2价值更高
   • 容量5: 物品1和物品2能够同时放下，总价值是两个物品价值之和，为 7.
   

2. 再加入物品3（重量是4，价值5）

   • 容量2: 只能放下物品1，最大价值为 3
   • 容量 3: 选择放物品2，最大价值为 4
   • 容量4: 选择放物品 3，最大价值能够达到 5
   • 容量 5: 选择不放物品3，最大价值是 7
   

3. 再加上物品 4（重量是5，价值是6）

   • 容量4: 根本放不下物品4，选择不放，最高价值和上一轮相同
   • 容量5: 有两种方案
     • 放物品4: 容量占满，最大价值为 6
     • 不放物品4，最大价值和上一轮相同，为 7，取较大者，因此最大总价值为 7
   

状态转移方程

dp[i][c] 里面的 i 代表第 i个物品，c 代表背包的容量。

• 不放物品 i：最大价值就和上一轮是相同的 dp[i-1][c]
• 放物品 i：最大价值 = 上一轮减去当前物品重量的容量对应的最大价值 + 当前这个物品的价值

然后看放入物品 i 和不放物品 i 哪一个价值更大，取价值较大的那一个。

代码实现

/* 0-1 背包：动态规划 */
// 1. 重量的数组
// 2. 价值的数组
// 3. 背包的容量
function knapsackDP(wgt, val, cap) {
  const n = wgt.length // 得到物品的数量

  // 接下来就初始化一个 dp 表，这个 dp 表就是一个二维数组
  const dp = new Array(n + 1).fill(0).map(() => new Array(cap + 1).fill(0))

  // 外层循环在遍历物品
  for (let i = 1; i <= n; i++) {
    // 内层循环在遍历背包容量
    for (let c = 1; c <= cap; c++) {
      if (wgt[i - 1] > c) {
        // 进入此分支，说明当前物品超过背包容量
        // 我们就不选择物品 i
        dp[i][c] = dp[i - 1][c]
      } else {
        // 当前物品没有超过背包容量，接下来就要看选不选物品i
        // 选不选取决于哪一种方案的价值更大
        dp[i][c] = Math.max(
          dp[i - 1][c],
          dp[i - 1][c - wgt[i - 1]] + val[i - 1]
        )
      }
    }
  }
  return dp[n][cap]
}

-EOF-