完全背包问题详解：从原理到实战
1. 引言
背包问题是动态规划中的一类经典问题，它描述了如何在有限容量的约束下，选择物品以获得最大价值。根据物品的可选次数，背包问题主要分为三种：0-1背包（每个物品最多选一次）、完全背包（每个物品可以选无限次）和多重背包（每个物品有次数限制）。其中，完全背包因其物品无限的性质，在实际问题中有着广泛的应用，例如找零钱、凑数、资源分配等。
本文将从基本概念入手，逐步推导完全背包的状态转移方程，并通过经典例题帮助读者掌握其核心思想和代码实现。
2. 完全背包问题定义
问题描述：有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的体积为 w[i]，价值为 v[i]。求解：将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
与0-1背包的唯一区别在于：每种物品的数量是无限的。这一差异直接导致了状态转移方程和代码遍历顺序的不同。
3. 与0-1背包的区别
在0-1背包中，我们使用二维数组 dp[i][j] 表示前 i 件物品恰放入容量为 j 的背包的最大价值，状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
由于物品只能选一次，当我们决定放入第 i 件物品时，必须从 i-1 件物品的状态转移过来。
而在完全背包中，物品可以无限选取，因此当我们决定放入一件第 i 种物品后，还可以继续放入更多的第 i 种物品。这意味着状态转移时，我们应该考虑在同一行（即同一物品）上的转移，而不是上一行。于是状态转移方程变为：
dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])
即放入一件第 i 种物品后，还可以继续考虑放入更多的第 i 种物品（仍处于第 i 行）。
4. 空间优化与遍历顺序
与0-1背包类似，我们可以将二维数组压缩为一维数组 dp[j]，表示容量为 j 时的最大价值。关键区别在于内层循环的遍历方向：
- 0-1背包：内层循环必须逆序遍历容量，以确保每个物品只被考虑一次（因为
dp[j - w[i]]还是上一行的值）。 - 完全背包：内层循环必须正序遍历容量，因为
dp[j - w[i]]可能已经包含了当前物品多次选取的结果，这正是我们想要的。
一维完全背包的代码模板如下：
def complete_knapsack(N, V, w, v):dp = [0] * (V + 1)for i in range(N):for j in range(w[i], V + 1): # 正序遍历dp[j] = max(dp[j], dp[j - w[i]] + v[i])return dp[V]
5. 经典例题分析
5.1 零钱兑换（LeetCode 322）
问题描述：给定不同面额的硬币 coins 和一个总金额 amount，计算凑成总金额所需的最少硬币个数。每种硬币数量无限。
背包视角：
- 物品：每种硬币
- 体积：硬币面值
- 价值：1（表示硬币个数）
- 目标：恰好装满背包，求最小价值
状态定义：dp[j] 表示凑成金额 j 所需的最少硬币数。初始化 dp[0]=0，其余为 inf。
转移方程：对于每个硬币 coin，有 dp[j] = min(dp[j], dp[j - coin] + 1)（j >= coin）。
代码实现：
def coinChange(coins, amount):dp = [float('inf')] * (amount + 1)dp[0] = 0for coin in coins:for j in range(coin, amount + 1):dp[j] = min(dp[j], dp[j - coin] + 1)return dp[amount] if dp[amount] != float('inf') else -1
5.2 完全平方数（LeetCode 279）
问题描述：给定正整数 n，找到若干个完全平方数（如 1, 4, 9, 16, ...）使其和等于 n，并且使用个数最少。每个平方数可重复使用。
背包视角：
- 物品：所有小于等于
n的平方数i*i - 体积：平方数值
- 价值：1
- 目标：恰好装满容量
n，求最小价值
状态定义：dp[j] 表示组成数 j 所需的最少平方数个数。初始化 dp[0]=0，其余为 inf。
转移方程：对于每个平方数 sq，有 dp[j] = min(dp[j], dp[j - sq] + 1)。
代码实现：
def numSquares(n):dp = [float('inf')] * (n + 1)dp[0] = 0squares = [i*i for i in range(1, int(n**0.5) + 1)]for sq in squares:for j in range(sq, n + 1):dp[j] = min(dp[j], dp[j - sq] + 1)return dp[n]
5.3 单词拆分（LeetCode 139）——一种变体
虽然单词拆分通常不被归类为背包问题，但其思想与完全背包高度相似：将字符串 s 视为背包容量，单词视为物品，每个单词可以重复使用，并且需要按顺序填充。其状态转移方程 dp[j] = dp[j] or (dp[j - len(word)] and s[j-len(word):j] == word) 正是完全背包的思想体现。读者可自行体会。
6. 完全背包的变种
- 求组合数：如“零钱兑换 II”（LeetCode 518），求凑成总金额的硬币组合数。此时状态转移方程为
dp[j] += dp[j - coin]，且内外层循环的顺序会影响结果是组合数还是排列数。通常求组合数时，外层遍历物品，内层正序遍历容量；求排列数时，外层遍历容量，内层遍历物品。 - 二维费用完全背包：物品有两种费用（如体积和重量），需同时考虑两个维度的限制。
- 完全背包求具体方案：在计算过程中记录决策，最后回溯得到选择了哪些物品。
7. 总结
完全背包是动态规划中的基础模型，掌握其核心要点对于解决许多实际问题至关重要。下面总结完全背包的关键点：
- 状态定义：
dp[j]表示容量为j时的最优值（最大或最小）。 - 转移方程：
dp[j] = opt(dp[j], dp[j - w[i]] + v[i])，其中opt根据问题取max或min。 - 遍历顺序：外层循环遍历物品，内层循环正序遍历容量。
- 初始化：根据问题要求（是否恰好装满、求最大还是最小）合理设置初始值。
- 适用场景：物品无限、需要填充一定容量、求最优值或方案数的问题。