动态规划之背包问题

发表于   |   分类于 ，

背包问题是动态规划的经典题型，今天就背包问题中经典的01背包问题和完全背包问题做一下复习。
图片

01背包问题

问题描述：有一个容量为W的背包，和N个物品，每个物品都有其相应的重量和价值。其中第i个物品的重量为 w[i]，价值为 v[i]。请问这个背包最多能装的价值是多少？

在取物品时，我们受到两个因素的影响：背包的剩余容量和所取的物品。

我们定义 f(w,k) 为 当背包剩余容量为w时，现有k件物品可以取，所能够取到的最大价值。

对于每件物品，我们有两种选择： 取或者不取。取与不取的条件便是背包的剩余容量，如果背包当前的剩余容量大于当前物品的重量，则该物品可以取，否则该物品不取。

当物品太重，当前物品不取时，能够取到的最大价值便是取到前一个物品的最大价值。即 w[k]>w时，f(w,k)=f(w,k-1)。

当背包容量大于当前物品重量时，当前物品可以取。那么最大价值便是 f(w,k)=max(f(w,k-1),f(w-w[k],k-1)+v[k])。

因此，状态转移公式：

1
2
3
4
         |-- f(w,k-1), w[k]>w (物品太重，背包放不下)
f(w,k) = |
         |-- max(f(w,k-1), f(w-w[k], k-1)+v[k]),  w[k]<=w

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 
 * @param weights 物品重量
 * @param values 物品价值
 * @param W 背包容量
 */

function solve(weights: number[], values: number[], W: number) {

  const n = weights.length;

  // 定义 dp[i][j] 为剩余背包容量为i，有前j件物品可以取时能够取到的最大价值
  const dp = new Array(W + 1).fill(0).map(() => new Array(n + 1).fill(0));

  for (let i = 1; i <= W; i++) {
    for (let j = 1; j <= n; j++) {
      // 物品在数组中的索引
      const idx = j - 1;
      if (weights[idx] > i) {
        // 背包容量不足
        dp[i][j] = dp[i][j - 1];
      } else {
        // 背包容量足够，取与不取之间取最大值
        dp[i][j] = Math.max(
          dp[i][j - 1],
          dp[i - weights[idx]][j - 1] + values[idx]
        );
      }
    }
  }

  return dp[W][n];
}

完全背包问题

完全背包是01背包的升级或变种，在01背包中，每件物品只有一件，因此在取的过程中，只能取0或1件。而在完全背包问题中，每件物品有无数件，每次取的时候，同一件物品可以取多次。

解决思路和01背包一致。

我们定义 f(w,k) 为当背包剩余容量为w时，现有k件物品可以取，所能够取到的最大价值。

同样，对于每件物品，也是有取和不取两种，其条件也是基于背包的剩余容量来判断。

当背包容量不足时，其状态转移和01背包一样，即 f(w,k)=f(w,k-1)。

不同点在于背包容量足够装下当前物品时的状态。由于物品可以取多次，因此在取了当前物品时，物品数量还是k，而非01背包的k-1，因此完全背包问题中背包容量足够时状态：

f(w,k)=max(f(w,k-1), f(w-w[k], k)+v[k])

最终的完全背包问题的状态转移公式为：

1
2
3
         |-- f(w,k-1), w[k]>w (物品太重，背包放不下)
f(w,k) = |
         |-- max(f(w,k-1), f(w-w[k])+v[k]), w[k]<=w

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const solve = function (weights: number[], values: number[], W: number) { 
  const n = weights.length;
  // 定义 dp[i][j] 为剩余背包容量为i，有前j件物品可以取时能够取到的最大价值
  const dp = new Array(W + 1).fill(0).map(() => new Array(n+1).fill(0));
  
  for (let i = 1; i <= W; i++) {
    for (let j = 1; j <= n; j++) {
      const idx = j - 1;
      if (weights[idx] > i) {
        // 背包容量不足
        dp[i][j] = dp[i][j - 1];
      } else {
        // 剩余容量足够，状态转移
        // 这里和01背包不同的地方在于dp[i-weights[idx]][j] + values[idx]
        dp[i][j] = Math.max(
          dp[i][j - 1],
          dp[i-weights[idx]][j] + values[idx]
        );
      }
    }
  }
  return dp[W][n];
}