hello-algo：完全背包问题的动态规划解法与空间优化——为什么内循环必须正序遍历

本篇基于《Hello 算法》（hello-algo）仓库中完全背包问题的代码与图解，完整讲解从二维 dp 表推导到一维空间优化的全过程：你将掌握完全背包与 0-1 背包在状态转移方程上唯一的差异（dp[i-1][c-w] 变为 dp[i][c-w]）、该差异如何决定内循环必须正序遍历这一关键结论，并能直接复现仓库中的 Python 示例（样例输入下最大价值为 22）与 C++ 对照实现。

问题定义与示例数据

给定 n 个物品，第 i 个物品的重量为 wgt[i-1]、价值为 val[i-1]，和一个容量为 cap 的背包。与 0-1 背包的唯一区别是：每个物品可以重复选取，要求计算在限定背包容量下能放入物品的最大价值。

仓库 完全背包 Python 实现 末尾的 Driver Code 使用了如下样例：

wgt = [1, 2, 3]
val = [5, 11, 15]
cap = 4

直觉上最优方案是选 2 个重量为 2 的物品（总重量 4，总价值 22）。实际运行该文件可验证，两个函数输出一致：

不超过背包容量的最大物品价值为 22
不超过背包容量的最大物品价值为 22

动态规划思路：状态转移方程与 0-1 背包的"一字之差"

完全背包问题与 0-1 背包问题非常相似，区别仅在于不限制物品的选择次数：

• 在 0-1 背包问题中，每种物品只有一个，将物品 i 放入背包后，只能从前 i-1 个物品中继续选择；
• 在完全背包问题中，每种物品数量无限，将物品 i 放入背包后，仍可以从前 i 个物品中选择（即物品 i 本身可以再次被选）。

据此，状态 dp[i][c]（考虑前 i 个物品、容量为 c 时的最大价值）的两种决策转移为：

• 不放入物品 i：转移至 dp[i-1][c]，与 0-1 背包相同；
• 放入物品 i：转移至 dp[i][c - wgt[i-1]]，注意下标是 i 而不是 i-1。

状态转移方程为：

dp[i][c] = max(dp[i-1][c], dp[i][c - wgt[i-1]] + val[i-1])

将 0-1 背包的 Python 实现 中 knapsack_dp 的转移式与本方程对比，可以确认：两道题的代码仅有一处从 dp[i - 1][c - wgt[i - 1]] 变为 dp[i][c - wgt[i - 1]]，其余完全一致。

二维 dp 表的完整实现

对应 codes/python/chapter_dynamic_programming/unbounded_knapsack.py#L8-L22 中的 unbounded_knapsack_dp：

def unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
    """完全背包：动态规划"""
    n = len(wgt)
    # 初始化 dp 表
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    # 状态转移
    for i in range(1, n + 1):
        for c in range(1, cap + 1):
            if wgt[i - 1] > c:
                # 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c]
            else:
                # 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
    return dp[n][cap]

逐点说明：

• dp 表尺寸：(n + 1) × (cap + 1)，全 0 初始化。首行 dp[0][c] 与首列 dp[i][0] 天然为 0（没有物品或没有容量时价值为 0），这与完全背包"不超过容量"的语义一致，不需要额外的 +∞ 处理；
• 容量越界分支：当 wgt[i-1] > c 时当前物品放不进去，只能不选，直接继承 dp[i-1][c]；
• 正常分支：取"不选"与"选一次物品 i"两种方案的最大值。选物品 i 之后，剩余容量 c - wgt[i-1] 内仍允许再选物品 i，这正是 dp[i][...]（同维度）带来的可重复选取语义。

时间复杂度为 O(n × cap)，空间复杂度为 O(n × cap)。

空间优化：与 0-1 背包相反，内循环改为正序遍历

二维表压缩为一维数组时，关键问题是遍历方向。由于当前状态 dp[c] 是从**左边（同行 c - w）和上边（上一行 c）**转移而来的，压缩后：

• 正序遍历时，dp[c - w] 已经是**本轮（第 i 个物品）**算出的新值——这恰好符合完全背包"放入物品 i 后仍可从物品 i 中继续选"的要求；
• 若改用倒序遍历，dp[c - w] 会被保护为上一行的旧值，物品 i 在一轮中最多只能选一次，就退化成 0-1 背包了。

这个遍历顺序与 0-1 背包正好相反，这一点可以直接从源码得到印证：knapsack.py 的 knapsack_dp_comp 内循环是 for c in range(cap, 0, -1)（倒序），而 unbounded_knapsack.py 的 unbounded_knapsack_dp_comp 内循环是 for c in range(1, cap + 1)（正序），源码注释也分别写着"倒序遍历"与"正序遍历"。

空间优化后的实现只需将 dp 数组的第一维删除：

def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
    """完全背包：空间优化后的动态规划"""
    n = len(wgt)
    # 初始化 dp 表
    dp = [0] * (cap + 1)
    # 状态转移
    for i in range(1, n + 1):
        # 正序遍历
        for c in range(1, cap + 1):
            if wgt[i - 1] > c:
                # 若超过背包容量，则不选物品 i
                dp[c] = dp[c]
            else:
                # 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
    return dp[cap]

注意转移式中 max 的左操作数 dp[c] 此时代表"不选"（保留旧值），右操作数 dp[c - wgt[i - 1]] + val[i - 1] 代表"选一次"，且右操作数引用的是本轮已更新的位置，从而在一维数组上隐式地完成了"无限次选取"。空间复杂度降至 O(cap)，时间复杂度仍为 O(n × cap)。

跨语言实现的一致性

从源码结构看，各语言实现保持了同一套逻辑与同一组样例数据。以 C++ 实现 为例：

/* 完全背包：空间优化后的动态规划 */
int unboundedKnapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<int> dp(cap + 1, 0);
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[c] = dp[c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[cap];
}

可以看到 Python 版中 range(1, cap + 1) 的正序遍历对应 C++ 中的 for (int c = 1; c <= cap; c++)，转移式与越界分支逐行对应。仓库中 Go、Java、Rust、TypeScript 等其他语言的实现同样遵循该模式，可分别在 codes/ 下对应语言的 chapter_dynamic_programming/unbounded_knapsack.* 文件中核对。

变体延伸：零钱兑换是完全背包的特例

背包问题是一大类动态规划问题的代表，其中零钱兑换问题就是完全背包的特例（详见 完全背包问题章节文档）。两者的联系与不同点：

• 可相互转换："物品"对应"硬币"、"物品重量"对应"硬币面值"、"背包容量"对应"目标金额"；
• 优化目标相反：完全背包最大化物品价值（max），零钱兑换最小化硬币数量（min）；
• 约束语义不同：完全背包求"不超过"容量的解，零钱兑换求"恰好"凑到目标金额的解。

因此在 coin_change.py 的 coin_change_dp 中，状态转移变为 dp[i][a] = min(dp[i-1][a], dp[i][a - coins[i-1]] + 1)，选中硬币时执行 +1 计数；而"恰好凑出"的要求通过哨兵值 MAX = amt + 1 实现——用 amt + 1 表示无效解（因为凑出 amt 最多只需 amt 枚硬币），既避免了整型最大值 +1 溢出，又方便 min 过滤无效解，最后若 dp[n][amt] == MAX 则返回 -1。空间优化版 coin_change_dp_comp 的写法与完全背包一致：一维数组 + 正序遍历 for a in range(1, amt + 1)。

小结与复杂度对照

维度	0-1 背包	完全背包
物品数量	每种 1 个	每种无限
选物品后的状态转移	dp[i-1][c - wgt[i-1]]	dp[i][c - wgt[i-1]]
一维优化时内循环	倒序 range(cap, 0, -1)	正序 range(1, cap + 1)
时间复杂度	O(n × cap)	O(n × cap)
空间复杂度（优化后）	O(cap)	O(cap)

掌握本文后可以验证几个要点：完全背包与 0-1 背包的全部差异浓缩在一维下标（i vs i-1）与遍历方向（正序 vs 倒序）上；空间优化的正确性完全由"左边的值是否应为本轮新值"这一需求决定。相关代码集中在 codes/python/chapter_dynamic_programming/unbounded_knapsack.py 与 codes/python/chapter_dynamic_programming/knapsack.py，可直接运行对比两者在相同输入下的行为差异；配套的逐步图解位于 完全背包章节文档 及其 unbounded_knapsack_problem.assets/ 图片目录中。