跳到主要内容

完全背包问题

如果每种物品有无限个，则是完全背包问题。

状态转移方程​

每次决策时，可以从NN中物品中选择一个，下次决策时，还可重复选，这就等价于无限个了。因此可选的动作有NN种。

取出一个物品后，由于每种物品的个数是无限个，所以物品的个数没有发生变化，依旧是无限的，但是背包的容量变小了，这里唯一的变量就是背包容量。因此我们定义函数 f(W)f(W)，表示背包容量为 WW 时能容纳的物品的最大价值。

至此，我们回答了4个问题：

  • 原子问题是 f(0)=0f(0)=0，即背包容量为0时，能容纳的物品的最大价值为0
  • 变量为背包容量 WW
  • 函数的返回值为能容纳的物品的最大价值
  • 可选的动作有2N2N种：对每种物品ii，选或不选

因此，可以得出状态转移方程如下：

f(W)={0W=0max⁡{f(W),f(W−wi)+vi}0≤i<Nf(W)=\begin{cases} 0 & W=0 \\ \max\left\{f(W),f(W-w_i)+v_i\right\} & 0 \leq i < N \end{cases}

在上面的公式中，第一个f(W)f(W)表示不选物品ii，第二个 f(W−wi)+vif(W-w_i)+v_i 表示选择物品ii后的最优解。如果f(W)f(W)更大，max()运算符会选择f(W)f(W)，不选第ii种物品；如果f(W−wi)+vif(W-w_i)+v_i更大，则会选择第ii种物品。由于 ii 每次可以重复选，精准表达了每种物品有无限个可用的意思。

代码框架​

根据状态转移方程，得出伪代码如下：

dp = [0] * (W+1)
for i in range(N): 
    for w in range(w[i], W+1): 
        dp[w]=max(dp[w],dp[j-w[i]]+v[i])

与 0-1 背包问题相比，仅有一行代码不同，这里内循环是顺序的，而 0-1 背包是逆序的（在使用滚动数组的情况下）。

为什么？在0-1背包问题中，内循环从右到左，是为了保证每个物品只选一次，保证在选择第i个物品时，依赖的是一个没有选择第i个物品的子结果f[i-1][j-w[i]]；而在完全背包问题中，内循环是从左到右的，选择第i个物品时，依赖了左边的f[i-1][j-w[i]]，它已经早先被更新了（因为从左到右更新的），此时f[i-1][j-w[i]]这个最优解，有可能选择了i物品，意味着重复选择了物品i，因此精准表达了物品有无限个。

抽象出处理单个物品的函数：

def unbounded_knapsack(f: List[int], i: int):
    for j in range(w[i], W+1):
        f[j]=max(f[j],f[j-w[i]]+v[i])

内外for循环的顺序​

  • 求最值，内外for循环可以任意颠倒。例如 Coin Change
  • 求组合数，外层for遍历物品，内层for循环遍历背包。例如 Coin Change II
  • 求排列数，外层for遍历背包，内层for循环遍历物品。例如 Combination Sum IV