完全背包问题[编辑 | 编辑源代码]

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

问题描述[编辑 | 编辑源代码]

给定一个容量为 $W$ 的背包，以及 $n$ 种物品，每种物品 $i$ 有一个重量 $w_{i}$ 和一个价值 $v_{i}$ 。每种物品的数量是无限的。目标是从这些物品中选择一些放入背包，使得背包中物品的总重量不超过 $W$ ，且总价值最大化。

动态规划解法[编辑 | 编辑源代码]

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

状态定义[编辑 | 编辑源代码]

设 $d p [w]$ 表示背包容量为 $w$ 时能够获得的最大价值。

状态转移方程[编辑 | 编辑源代码]

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

实现代码[编辑 | 编辑源代码]

以下是完全背包问题的动态规划实现（以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

代码解释[编辑 | 编辑源代码]

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

优化空间复杂度[编辑 | 编辑源代码]

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

优化后的代码[编辑 | 编辑源代码]

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

优化解释[编辑 | 编辑源代码]

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

实际应用案例[编辑 | 编辑源代码]

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

货币找零示例[编辑 | 编辑源代码]

以下是一个货币找零问题的实现（求最少硬币数）：

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)

总结[编辑 | 编辑源代码]

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

扩展阅读[编辑 | 编辑源代码]