完全背包问题

在「0-1 背包问题」的基础上，去掉「每个物品只有一件」的限制，即总重量不超过背包承重，且每个物品有无数多件，问背包能装下物品的最大价值总和是多少。这是「完全背包」问题的描述。

有 N 种重量和价值分别为 wi 和 vi 的物品。从这些物品中挑选总重量不超过 W 的物品，求出挑选物品价值总和的最大值。每种物品可以挑选任意多件。

提示：
1≤N≤100
1≤w__i,v__i≤100
1≤W≤1000

输入：
N = 3 
w = [3, 4, 2]
v = [40, 50, 30]
W = 7
输出：100

题意分析：「完全背包问题」的重点在于：

• 每种物品都有无限件可用；
• 一种物品可以使用多个，且不计算顺序。

思路分析：

延续「0-1 背包问题」的状态定义，进行状态转移方程的推导。

状态定义

dp[i][j]表示：考虑物品区间 [0..i] 里，不超过背包容量 j，能够获得的最大价值总和。

在状态转移的时候，每一件物品在背包有限制的前提下可以使用多少个需要全部考虑进去的。「动态规划」的基本思想依然是 枚举所有的可能方案，就是下面的式子里变量 k 的含义。

状态转移方程：

初始化

当只有 1 个物品的时候，只要当前物品的重量的 整数倍数 的物品的重量总和不超过最大承重，都可以装入背包。因此初始化的时候需要枚举下标为 0 的物品在当前限制的最大承重下可以装入多少个。

未优化的代码

backpackComplete(W, weights, values) {
  const N = weights.length;
  if (N == 0) {
    return 0;
  }
  // dp[i][j] 表示：考虑物品区间 [0..i] 里，不超过背包容量 j，能够获得的最大价值总和
  // 由于包含价值为 0 的计算，所以 + 1
  const dp = new Array(N).fill(0).map(() => new Array(W + 1).fill(0));
  // 初始化：先写第 1 行
  for (let k = 0; k * weights[0] <= W; k++) {
    dp[0][k * weights[0]] = k * values[0];
  }
  // 递推开始
  for (let i = 1; i < N; i++) {
    for (let j = 0; j <= W; j++) {
      // 多一个 for 循环，枚举下标为 i 的物品可以选择的个数
      for (let k = 0; k * weights[i] <= j; k++) {
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * weights[i]] + k * values[i]);
      }
    }
  }
  return dp[N - 1][W];
}

复杂度分析：

• 时间复杂度：O(NW)，这里 N 是背包价值数组的长度，W 是背包的容量，使用了三重循环
• 空间复杂度：O(NW)

这一版代码的时间复杂度很高，存在重复计算

优化公式推导

1. 初始状态转移方程：f[i, j] = max(f[i-1, j-w[i]*k] + v[i]*k) (代码是三重循环，时间复杂度很高，需要简化)
   1. f[i, j] = Max(f[i-1, j], ``f[i-1, j-w]+v, f[i-1, j-2w]+2v, f[i-1, j-3w]+3v, ...``)
   2. f[i, j-w] = Max( ``f[i-1, j-w], f[i-1, j-2w]+v, f[i-1, j-2w]+2v,...``)
2. 观察发现：蓝色部分只是比绿色部分多了一个 v
   1. 结论：f[i, j] = f[i, j-w] + v
   2. 所以状态转移方程是：**dp[i][j]=max(dp[i−1][j],dp[i][j−w[i]]+v[i])**

      优化的状态转移方程

• 「0-1 背包问题」的状态转移方程：

dp[i][j]=max(dp[i−1][j],dp[**i−1**][j−w[i]]+v[i])

• 「完全背包问题」的状态转移方程：

dp[i][j]=max(dp[i−1][j],dp[**i**][j−w[i]]+v[i])

区别只在红色标出来的地方：

1. 「0-1 背包问题」参考上一行的值，「完全背包」参考当前行的值。
2. 所以优化空间的写法使用一维数组的时候
   1. 「0-1 背包问题」倒序填表
   2. 「完全背包问题」正序填表