完全背包

完全背包和 0/1 背包 几乎一模一样，唯一区别：每件物品可以无限次使用。

跟 0/1 的差异：一个下标

转移方程对比：

差异只有一个下标 —— “选第 i 件”那一支，0/1 看的是上一行 dp[i-1][j - wᵢ]（这一轮还没选过它），完全背包看的是当前行 dp[i][j - wᵢ]（这一轮可能已经选了几件了，还能继续选）。

直觉

想象沿着第 i 行从左到右填表：

• 来到 dp[i][j] 时，dp[i][j - wᵢ] 已经计算过（在左边）
• 如果决定再装一件第 i 件，剩余容量 j - wᵢ 下的最优解就是 dp[i][j - wᵢ]，加上一件第 i 件的价值 vᵢ
• 由于 dp[i][j - wᵢ] 本身可能已经选过若干第 i 件，所以这种递推自然支持”无限次使用”

滚动数组的关键差异

0/1 背包用滚动数组时 j 必须倒序枚举（防止重复选）；完全背包恰恰相反：

for (int i = 1; i <= n; ++i)
  for (int j = w[i-1]; j <= W; ++j)  // 完全背包：正序！
    dp[j] = max(dp[j], dp[j - w[i-1]] + v[i-1]);

正序时 dp[j - wᵢ] 已经是”本轮可能装过若干件”的状态，正好符合完全背包的语义。

一句话记忆：0/1 倒序，完全正序，差别就是一个下标和一个循环方向。

复杂度

• 时间：O(n·W)
• 空间：O(n·W) 二维 / O(W) 滚动数组

常见题型

• 凑硬币（已有专题页）—— 求最少硬币数，本质是 min 版完全背包
• 字符串切分（“单词拆分”）—— 把字符串看成容量，单词看成物品
• 整数划分

在动画里看什么

跟 0/1 背包对照看，唯一不同的是”选”那条弧线：

• 0/1：弧线从左上方的 dp[i-1][j-wᵢ] 拉过来
• 完全：弧线从正左方的 dp[i][j-wᵢ] 拉过来（同一行更左的格子）

这一点不同在动画里能看得很清楚。