动态规划：完全背包问题与空间复杂度优化

描述
完全背包问题（Unbounded Knapsack Problem）是经典的优化问题之一。与0-1背包问题中每个物品最多只能选择一次不同，在完全背包问题中，每种物品都有无限件可供选择。给定一个容量为 \(C\) 的背包，和 \(n\) 种物品，每种物品 \(i\) 有一个重量 \(w_i\) 和价值 \(v_i\)。目标是在不超过背包容量的前提下，选择若干件物品（每种物品可以选择任意多件），使得装入背包的物品总价值最大。

解题过程循序渐进讲解

第一步：问题建模与状态定义

首先明确状态。设 \(dp[i][c]\) 表示“考虑前 \(i\) 种物品（即物品编号从 1 到 \(i\) ），在背包容量恰好为 \(c\) 时，所能获得的最大价值”。这里“恰好”可以避免初始化时的特殊处理，最终答案是 \(\max_{0 \le c \le C} dp[n][c]\)。另一种常见定义是“容量不超过 \(c\) 时的最大价值”，此时答案为 \(dp[n][C]\)，初始化略有不同。我们采用“恰好”定义来清晰推导。

第二步：基本状态转移方程推导

考虑第 \(i\) 种物品，在容量 \(c\) 下，我们可以选择 0 件、1 件、2 件…直到放不下为止。
若选择 0 件，则最大价值为 \(dp[i-1][c]\)（只考虑前 \(i-1\) 种物品）。
若选择 \(k\) 件（\(k \ge 1\) 且 \(k \cdot w_i \le c\)），则占用 \(k \cdot w_i\) 的容量，获得 \(k \cdot v_i\) 的价值，剩余容量 \(c - k \cdot w_i\) 由前 \(i\) 种物品填充（注意这里仍是前 \(i\) 种，因为虽然第 \(i\) 种用了 \(k\) 件，但还可以继续用前 \(i\) 种填充剩余容量）。但更优的推导方式如下：

实际上，当我们考虑 \(dp[i][c]\) 时，可以分两种情况：

1. 不选第 \(i\) 种物品：\(dp[i][c] = dp[i-1][c]\)。
2. 至少选 1 件第 \(i\) 种物品：那么我们可以先“放进去一件”第 \(i\) 种物品，占用了 \(w_i\) 重量，获得 \(v_i\) 价值，之后背包剩下 \(c - w_i\) 的容量，此时仍然可以考虑前 \(i\) 种物品（因为第 \(i\) 种还能继续选），即状态为 \(dp[i][c - w_i]\)。
   于是：\(dp[i][c] = \max( dp[i-1][c],\ dp[i][c - w_i] + v_i )\)，其中要求 \(c \ge w_i\)。

注意第二种情况是 \(dp[i][c - w_i]\)，不是 \(dp[i-1][c - w_i]\)，这正是完全背包与0-1背包的核心区别。
这个方程是“至少选一件”的等价表达，它通过将问题递归到同一种物品的更小容量子问题，巧妙涵盖了选任意多件的情况，而不需要显式枚举 k。

第三步：初始化和边界处理

• 初始化 \(dp[0][0] = 0\)，表示考虑 0 种物品，容量恰好为 0 时最大价值为 0。
• 对于 \(c > 0\)，\(dp[0][c] = -\infty\)（或一个很小的负数），因为不可能用 0 种物品凑出正容量，这样后续取 max 时会自动淘汰不可行状态。
• 对于 \(dp[i][0] = 0\)（容量 0 只能装价值 0）。
• 转移时，如果 \(c < w_i\)，则不能选第 i 种物品，所以 \(dp[i][c] = dp[i-1][c]\)。

第四步：空间复杂度优化（一维数组）

观察转移方程：
\(dp[i][c]\) 只依赖于：

1. 同一行前面的列：\(dp[i][c - w_i]\)（当 \(c \ge w_i\)）。
2. 上一行同一列：\(dp[i-1][c]\)。

如果使用一维数组 \(f[c]\) 表示当前处理到第 i 种物品时容量 c 的最大价值，那么更新顺序就很重要。
在0-1背包中，因为依赖 \(dp[i-1][c-w_i]\)，所以内循环需要从 C 递减到 w_i，避免覆盖上一行的值。
但在完全背包中，我们依赖的是 \(dp[i][c-w_i]\)，也就是更新后的当前行的值，所以内循环应该正向枚举 c 从 w_i 到 C。

具体操作：
初始化 \(f[0] = 0\)，其余 \(f[c] = -\infty\)。
对于每种物品 i，对于容量 c 从 w_i 到 C 递增：
\(f[c] = \max( f[c],\ f[c - w_i] + v_i )\)。

这里的 \(f[c]\) 在更新前实际上存储的是 \(dp[i-1][c]\)，更新后变为 \(dp[i][c]\)。正向更新时，当计算 \(f[c]\) 时，\(f[c-w_i]\) 可能已经被更新成本轮的 \(dp[i][c-w_i]\)，正好满足完全背包的依赖要求。

第五步：算法实现示例（Python）

def unbounded_knapsack(C, weights, values):
    n = len(weights)
    dp = [float('-inf')] * (C + 1)
    dp[0] = 0
    for i in range(n):
        w, v = weights[i], values[i]
        for c in range(w, C + 1):
            if dp[c - w] != float('-inf'):
                dp[c] = max(dp[c], dp[c - w] + v)
    return max(dp)  # 因为定义是“恰好”，所以取所有容量最大值

如果定义是“不超过容量”，则初始化 \(dp[0..C] = 0\)，且返回 \(dp[C]\)。

第六步：与0-1背包对比与理解

• 0-1背包：每种物品最多选1次，状态转移为 \(dp[i][c] = \max(dp[i-1][c], dp[i-1][c-w_i] + v_i)\)，优化后内循环倒序。
• 完全背包：每种物品无限次，状态转移为 \(dp[i][c] = \max(dp[i-1][c], dp[i][c-w_i] + v_i)\)，优化后内循环正序。

这是因为完全背包允许在同一轮考虑中重复选取当前物品，正序更新使得较小的 c-w_i 已更新为包含当前物品可选的最优解，从而在更新较大的 c 时能够利用“已选若干件当前物品”的结果。

第七步：扩展与相关问题

1. 恰好装满 vs 不要求装满：初始化不同，若要求恰好装满，则只有 dp[0]=0 合法，其余为 -∞；若不要求装满，则全初始化为 0。
2. 求方案数：将 max 改为加法计数，且初始化 dp[0]=1，其余为 0。
3. 求最小物品数：将 max 改为 min，且 dp[0]=0，其余为 ∞。

通过以上步骤，我们清晰地理解了完全背包的动态规划推导、空间优化原理，以及其与0-1背包的核心差异。