完全背包问题

什么是完全背包

完全背包（Unbounded Knapsack） 是动态规划中的经典问题：

有 n 种物品，每种物品有重量/价值 w_i，每种物品可以无限次使用，求恰好凑成重量 W 的方案数或最大价值。

特点

1. 物品数量无限：每种物品可以重复使用多次
2. 状态无后效性：只关心当前重量，不关心用了哪些物品
3. 组合方式：求的是组合（无序）还是排列（有序）

做题方法

核心思路：将大问题拆分为小问题

1. 定义状态：dp[j] 表示凑成重量 j 的方案数/最大价值
2. 初始条件：dp[0] = 1（方案数）或 dp[0] = 0（价值）
3. 状态转移：
   • 方案数：dp[j] += dp[j - w_i]
   • 最大价值：dp[j] = max(dp[j], dp[j - w_i] + value_i)
4. 遍历顺序：
   • 有序：先遍历目标 j，再遍历物品 i（顺序不同算不同）
   • 无序：先遍历物品 i，再遍历目标 j（顺序不同视为相同）

---

完全背包 vs 0-1 背包

0-1 背包（倒序）

for i in range(n):
    for j in range(W, weight[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

完全背包（正序）

for i in range(n):
    for j in range(weight[i], W + 1):
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

---

最大价值问题

问题描述

有 N 种物品，每种物品有重量 w_i 和价值 v_i，每种物品可以使用无限次，求在不超过背包容量 W 的情况下，选择物品使得总价值最大。

解法

定义：dp[j] 为背包容量为 j 时的最大价值

初始条件：dp[j] = 0（容量为 0 时价值为 0）

状态转移： dp[j] = max (dp[j], dp[j − w_i] + v_i)

代码实现

# 完全背包 - 一维 DP
N, W = map(int, input().split())
dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for j in range(w, W + 1):
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[W])

时间复杂度：O(N × W) 空间复杂度：O(W)

注意: 完全背包中内层循环需要正序遍历，因为每种物品可以使用多次。