编辑“︁完全背包问题”︁

= 完全背包问题 =

'''完全背包问题'''是动态规划中的经典问题之一，是[[0-1背包问题]]的变种。在完全背包问题中，每种物品可以选取无限次，而不仅仅是0次或1次。这使得问题在求解时需要采用不同的状态转移方程。

== 问题描述 ==
给定一个容量为<math>W</math>的背包，以及<math>n</math>种物品，每种物品<math>i</math>有一个重量<math>w_i</math>和一个价值<math>v_i</math>。每种物品的数量是无限的。目标是从这些物品中选择一些放入背包，使得背包中物品的总重量不超过<math>W</math>，且总价值最大化。

== 动态规划解法 ==
完全背包问题可以通过动态规划高效求解。与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>时的最大价值。

== 优化空间复杂度 ==
与0-1背包问题不同，完全背包问题的状态转移可以优化为一维数组，并且内层循环的顺序是从小到大（因为物品可以重复选择）。

=== 优化后的代码 ===
<syntaxhighlight lang="python">
def complete_knapsack_optimized(W, weights, values):
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        for w in range(weights[i], W + 1):
            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_optimized(W, weights, values))  # 输出: 15
</syntaxhighlight>

=== 优化解释 ===
1. 外层循环遍历物品，内层循环遍历容量（从小到大）。
2. 由于内层循环是顺序的，同一个物品可以被多次选择（即完全背包的特性）。

== 实际应用案例 ==
完全背包问题在现实生活中有广泛的应用，例如：
1. '''货币找零问题'''：给定无限数量的不同面额的硬币，求凑成某个金额的最少硬币数。
2. '''资源分配问题'''：在有限的资源下，选择无限供应的某些资源以最大化收益。
3. '''生产调度问题'''：在有限的生产能力下，选择生产某些产品以最大化利润。

=== 货币找零示例 ===
以下是一个货币找零问题的实现（求最少硬币数）：
<syntaxhighlight lang="python">
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] = min(dp[a], dp[a - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# 示例输入
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # 输出: 3 (5 + 5 + 1)
</syntaxhighlight>

== 总结 ==
完全背包问题是动态规划中的重要问题，与0-1背包问题的主要区别在于物品可以无限次选择。通过合理设计状态转移方程和一维数组优化，可以高效求解。实际应用中，完全背包问题广泛用于资源分配、货币找零等场景。

== 扩展阅读 ==
* [[0-1背包问题]]
* [[多重背包问题]]
* [[动态规划基础]]

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:动态规划]]