编辑“︁完全背包问题”︁（章节）

== 动态规划解法 ==
完全背包问题可以通过动态规划高效求解。与0-1背包问题不同，完全背包允许每种物品被选取多次，因此在状态转移时需要调整策略。

=== 状态定义 ===
设<math>dp[w]</math>表示背包容量为<math>w</math>时能够获得的最大价值。

=== 状态转移方程 ===
对于每种物品<math>i</math>，我们可以选择放入0次、1次、2次……直到背包容量不足以再放入该物品为止。因此，状态转移方程为：
<math>
dp[w] = \max(dp[w], dp[w - w_i] + v_i)
</math>
其中，<math>w_i \leq w \leq W</math>。

=== 实现代码 ===
以下是完全背包问题的动态规划实现（以Python为例）：

<syntaxhighlight lang="python">
def complete_knapsack(W, weights, values):
    n = len(weights)
    dp = [0] * (W + 1)
    
    for w in range(W + 1):
        for i in range(n):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[W]

# 示例输入
W = 10
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]

print(complete_knapsack(W, weights, values))  # 输出: 15
</syntaxhighlight>

=== 代码解释 ===
1. 初始化一个长度为<math>W + 1</math>的数组<code>dp</code>，用于存储每个容量下的最大价值。
2. 遍历每个容量<math>w</math>（从0到<math>W</math>）。
3. 对于每个物品<math>i</math>，如果其重量不超过当前容量<math>w</math>，则更新<code>dp[w]</code>为选择或不选择该物品的最大值。
4. 最终<code>dp[W]</code>即为背包容量为<math>W</math>时的最大价值。