动态规划解决背包问题（完全背包）

题目描述：
给定一个容量为 capacity 的背包和 n 种物品，每种物品有无限个可用。第 i 种物品的重量为 weights[i]，价值为 values[i]。求解将哪些物品装入背包，使得这些物品的总重量不超过背包容量，且总价值最大。输出最大总价值。

解题过程：

1. 问题分析
与 0-1 背包问题（每种物品最多选一次）不同，完全背包问题中每种物品可以选择任意多次（无限供应）。这导致状态转移方程和遍历顺序需要调整。

2. 定义状态
我们定义 dp[j] 表示容量为 j 的背包能够装载物品的最大价值。这里使用一维数组（滚动数组）来优化空间复杂度。

3. 状态转移方程
对于每种物品 i，我们考虑在容量 j 下是否选择该物品：

• 如果不选，则 dp[j] 保持不变。
• 如果选，由于物品无限供应，我们可以在容量允许的情况下多次选择，因此状态从 dp[j - weights[i]] 转移而来。

状态转移方程为：

dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

4. 遍历顺序
关键点在于内层循环（容量 j）的遍历顺序：

• 必须正序遍历 j 从 weights[i] 到 capacity。
• 原因：正序允许重复选取当前物品。当计算 dp[j] 时，dp[j - weights[i]] 可能已经包含当前物品，从而实现多次选择。

5. 初始化

• dp[0] = 0，表示容量为 0 的背包价值为 0。
• 其他 dp[j] 初始化为 0，确保后续 max 操作正确更新价值。

6. 算法实现

def knapsack_complete(capacity, weights, values):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):  # 遍历每种物品
        for j in range(weights[i], capacity + 1):  # 正序遍历容量
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[capacity]

7. 示例验证
假设 capacity = 5, weights = [1, 2, 3], values = [2, 3, 4]：

• 初始化 dp = [0, 0, 0, 0, 0, 0]
• 物品 0（重量 1，价值 2）：
  j=1：dp[1] = max(0, dp[0]+2=2) = 2
j=2：dp[2] = max(0, dp[1]+2=4) = 4（选两个物品 0）
  最终 dp = [0, 2, 4, 6, 8, 10]（容量 5 时全选物品 0）
• 物品 1（重量 2，价值 3）：
  j=2：dp[2] = max(4, dp[0]+3=3) = 4
j=4：dp[4] = max(8, dp[2]+3=7) = 8
• 物品 2（重量 3，价值 4）：
  j=3：dp[3] = max(6, dp[0]+4=4) = 6
j=5：dp[5] = max(10, dp[2]+4=8) = 10
  结果：最大价值为 10（5 个物品 0）。

8. 复杂度分析

• 时间复杂度：O(n × capacity)
• 空间复杂度：O(capacity)

关键区别：与 0-1 背包的内层逆序遍历不同，完全背包通过正序遍历实现物品的无限次选择。