完全背包

动态规划 · 无限次取

同一件，可以拿很多个

完全背包和 0-1 背包只差一个字：0-1 背包每件物品要么装一次、要么不装；完全背包里每件物品有无限多个，同一件可以反复装（只要不超重）。物品仍各有重量和价值，问在容量内怎么装总价值最大。

唯一的差别：「取」看哪一行

状态定义和 0-1 完全一样：dp[i][w] = 考虑前 i 种物品、容量 w 时的最大价值。装不下时也一样——沿用上一行 dp[i-1][w]。差别只在装得下那一步的「取」：

0-1 背包「取」是 dp[i-1][w-重量] + 价值——用的是上一行，意味着「取了这件就换下一件」；完全背包「取」是 dp[i][w-重量] + 价值——用的是本行，意味着「取了这件还能再取同一件」。代码上就是把一个下标 i-1 改成 i，可视化上「取」的来源格从左上方挪到了同一行的左侧。

下面固定 3 种物品 A(重2,值5) B(重3,值6) C(重4,值7)、容量 6。点「下一步」逐格看：当前格琥珀环，「不取」的上一行格和「取」的本行左侧格都黄色高亮——填入即变绿。留意第 1 行（只有 A）：容量 6 的格子一路 0→5→10→15，靠的全是本行左侧格，正是把 A 装了 3 个。走到底右下角 = 15（A×3：重 2×3=6、值 5×3=15）；同样这批物品若按 0-1 只能拿 12。右侧代码随每一步同步高亮。

	1	2	3	4	5	6
∅	0	0	0	0	0	0
A
B
C

边界：没有物品（第 0 行）或容量为 0（第 0 列）时，最大价值都是 0

1function completeKnapsack(w: number[], v: number[], W: number): number {
const m = w.length;
const dp = Array.from({ length: m + 1 }, () => Array(W + 1).fill(0));
for (let i = 1; i <= m; i++) {
  for (let c = 1; c <= W; c++) {
    if (w[i - 1] > c) {
      dp[i][c] = dp[i - 1][c];
    } else {
      dp[i][c] = Math.max(
        dp[i - 1][c], dp[i][c - w[i - 1]] + v[i - 1]); // 取来自本行 i
    }
  }
}
return dp[m][W];
15}

容量6

物品A(重2,值5) B(重3,值6) C(重4,值7)

1 / 20

正因为「取」可以停在本行，一次从左往右扫容量的过程中，同一件物品就被反复利用了——这就是完全背包允许重复的本质。其余套路和 0-1 完全相同：O(物品数 × 容量) 逐格填表、后面的直接查表复用。

完全背包在哪里用

硬币找零 / 凑数：每种面额硬币不限个数，凑出目标金额的最少枚数或方案数。
无限资源下料：同规格材料无限供应，求最优切割 / 装载。
DP 变体家族：把「取」的来源在上一行（0-1）与本行（完全）之间切换，是理解背包问题族的关键；再加上「次数有限」就成了多重背包。

建议和 0-1 背包两页对照着看——同一张表、同一套递推，只有「取」看上一行还是本行之差，却决定了每件物品能拿几个。

算法可视化

完全背包

同一件，可以拿很多个

唯一的差别：「取」看哪一行

完全背包在哪里用