02-背包DP

背包DP

模板

0-1 背包（倒序）

N, W = map(int, input().split())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
dp = [0] * (W + 1)

for i in range(N):
    for j in range(W, w[i] - 1, -1):        # 倒序：每件物品只用一次
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

print(dp[W])

完全背包（正序）

N, W = map(int, input().split())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
dp = [0] * (W + 1)

for i in range(N):
    for j in range(w[i], W + 1):            # 正序：每种物品可无限次用
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

print(dp[W])

多重背包（二进制拆分 → 0-1 背包）

N, W = map(int, input().split())
items = []

for _ in range(N):
    w, v, c = map(int, input().split())     # 重量、价值、数量
    k = 1
    while c > 0:
        take = min(k, c)
        items.append((w * take, v * take))  # 拆成 1,2,4,... 件的捆绑物品
        c -= take
        k *= 2

dp = [0] * (W + 1)
for w, v in items:
    for j in range(W, w - 1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[W])

解释

背包问题：将有限容量的容器用物品的子集填满，计算或优化与物品相关的数量。每个物品有正重量，所选物品总重量不得超过容量。常见变体：

• 0/1 背包：每件物品选或不选，总价值最大
• 完全背包：每种物品无限件，求最大价值或恰好凑满的方案数
• 多重背包：每种物品有限 $c_i$ 件
• 计数问题：有多少种方式恰好填满容器（顺序可能重要也可能不重要）

做题方法

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

0-1 背包为什么要倒序？

原因：避免同一物品被重复使用。以物品 (w=3, v=5)、W=6 为例，初始 dp=[0,0,0,0,0,0,0]：

正序遍历（错误）：

for j in range(w, W + 1):  # 正序
    dp[j] = max(dp[j], dp[j-w] + v)

j=3: dp[3] = max(0, dp[0]+5) = 5    # 放了这个物品
j=4: dp[4] = max(0, dp[1]+5) = 5    # dp[1] 是 0
j=5: dp[5] = max(0, dp[2]+5) = 5    # dp[2] 是 0
j=6: dp[6] = max(0, dp[3]+5) = max(0, 5+5) = 10   # 出问题了！

dp[3] 刚被更新成 5，dp[6] 又去查 dp[3]，相当于同一个物品用了两次。

倒序遍历（正确）：

j=6: dp[6] = max(0, dp[3]+5) = 5    # dp[3] 还是 0（未被当前物品更新）
j=5: dp[5] = max(0, dp[2]+5) = 5    # dp[2] 还是 0
j=4: dp[4] = max(0, dp[1]+5) = 5    # dp[1] 还是 0
j=3: dp[3] = max(0, dp[0]+5) = 5    # dp[0] 是 0

倒序时大 j 先更新，用到的 dp[j-w] 还是旧值，没被当前物品污染。

0-1 背包的二维写法

定义：dp[i][j] 为考虑前 i 件物品、容量为 j 时的最大价值；初始 dp[0][j] = 0。

$$dp[i][j] = \max(dp[i-1][j],\ dp[i-1][j-w_i] + v_i)$$

N, W = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]

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

print(dp[N][W])

时间 O(N × W)，空间 O(N × W)；一维滚动数组即上面的倒序模板，空间降到 O(W)。

例题

例题 1：Book Shop（0-1 背包模板题）

来源：CSES - Book Shop

给定 n 本书，每本书有价格 $h_i$ 和页数 $s_i$，总预算为 x，求在预算范围内能获得的最大页数。每本书只能购买一次。

限制：$1 \le n \le 1000$，$1 \le x \le 10^5$，$1 \le h_i, s_i \le 1000$。

示例：输入 4 10，h = [4, 8, 5, 3]，s = [5, 12, 8, 1]；输出 13（购买第 1 和第 3 本书，价格 4+5=9，页数 5+8=13）。

思路：0-1 背包。dp[j] 为花费不超过 j 时能获得的最大页数，转移 $dp[j] = \max(dp[j],\ dp[j - h_i] + s_i)$，倒序遍历。

n, x = map(int, input().split())
cost = [int(x) for x in input().split()]
pages = [int(x) for x in input().split()]

dp = [0] * (x + 1)

for i in range(n):
    for j in range(x, cost[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - cost[i]] + pages[i])

print(dp[x])

复杂度：时间 O(n × x)，空间 O(x)。

例题 2：Money Sums（0-1 背包求可行性）

来源：CSES - Money Sums

给定 n 枚硬币，每枚硬币价值 $x_i$，求能凑成的所有不同金额。

限制：$1 \le n \le 100$，$1 \le x_i \le 1000$。

示例：输入 4，coins = [4, 2, 5, 2]；输出 9 种金额：2 4 5 6 7 8 9 11 13。

思路：可行性背包。dp[j] 表示能否凑成金额 j，初始 dp[0] = True，转移 $dp[j] = dp[j]\ \text{或}\ dp[j - x_i]$，倒序保证每枚硬币只用一次。

n = int(input())
coins = list(map(int, input().split()))

max_sum = sum(coins)
dp = [False] * (max_sum + 1)
dp[0] = True

for coin in coins:
    for j in range(max_sum, coin - 1, -1):
        if dp[j - coin]:
            dp[j] = True

res = [i for i in range(1, max_sum + 1) if dp[i]]

print(len(res))
print(*res)

复杂度：时间 O(n × max_sum)，空间 O(max_sum)。

例题 3：Two Sets II（0-1 背包求方案数）

来源：CSES - Two Sets II

给定数字 1, 2, …, n，求将其分成两个和相等集合的方式数（对 $10^9+7$ 取模）。

限制：$1 \le n \le 500$。

示例：输入 7，输出 4。

思路：计数背包。总和 $S = n(n+1)/2$ 为奇数输出 0；否则数字 n 一定在较大组（较小组最多凑到 $n(n-1)/2 < S/2$），用 1~n-1 凑 $S/2$ 的方案数即答案。dp[j] 为凑成和 j 的方式数，dp[0] = 1，转移 $dp[j] = dp[j] + dp[j - i]$（倒序，取模）。

import sys

MOD = 10**9 + 7

n = int(input())

sum_elem = n * (n + 1) // 2

if sum_elem % 2 == 1:
    print(0)
    sys.exit()

target = sum_elem // 2

dp = [0] * (target + 1)
dp[0] = 1

for i in range(1, n):
    for j in range(target, i - 1, -1):
        dp[j] = (dp[j] + dp[j - i]) % MOD

print(dp[target])

复杂度：时间 O(n × target)，空间 O(target)。

例题 4：Dice Combinations（完全背包计数·序列）

来源：CSES - Dice Combinations

给定目标整数 $N$，计算有多少种骰子投掷序列使得点数和为 $N$（对 $10^9+7$ 取模）。

限制：$1 \le N \le 10^6$。

思路：完全背包计数（每种点数可无限次用，顺序不同算不同）。dp[i] 为和为 i 的序列数，dp[0] = 1，考虑最后掷出的点数得转移为前六项之和：

$$dp[i] = dp[i-1] + dp[i-2] + \dots + dp[i-6]$$

滚动写法只需最近 6 项：

MOD = 10**9 + 7
n = int(input())
dp = [1]

for i in range(n):
    total = sum(dp[-6:])
    dp.append(total % MOD)

print(dp[-1])

复杂度：时间 O(N)，空间 O(N)。

例题 5：Coin Combinations I（完全背包计数·有序）

来源：CSES - Coin Combinations I

给定 n 种硬币价值 $c_i$，求凑成金额 x 的方式数（顺序不同视为不同），模 $10^9+7$。

限制：$1 \le n \le 100$，$1 \le x \le 10^6$，$1 \le c_i \le 10^6$。

示例：输入 3 9，coins = [2, 3, 5]；输出 8。

思路：有序计数——先遍历金额、再遍历硬币。dp[w] 为凑成 w 的方式数，dp[0] = 1，转移 $dp[w] = \sum_i dp[w - c_i]$。

MOD = 10**9 + 7

n, x = map(int, input().split())
coins = list(map(int, input().split()))

dp = [0] * (x + 1)
dp[0] = 1
for i in range(1, x + 1):
    for c in coins:
        if i - c >= 0:
            dp[i] = (dp[i] + dp[i - c]) % MOD

print(dp[x])

复杂度：时间 O(n × x)，空间 O(x)。

例题 6：Coin Combinations II（完全背包计数·无序）

来源：CSES - Coin Combinations II

同上，但求无序方式数（顺序不同视为相同）。

示例：输入 3 9，coins = [2, 3, 5]；输出 3（只计 {2,2,5}、{3,3,3}、{2,2,2,3}）。

思路：无序计数——交换两层循环，先遍历硬币、再遍历金额，每种硬币组合只计一次：

import sys
MOD = 10**9 + 7
input = sys.stdin.readline

n, x = map(int, input().split())
coins = list(map(int, input().split()))

dp = [0] * (x + 1)
dp[0] = 1

for c in coins:
    for i in range(x + 1):
        if i - c >= 0:
            dp[i] = (dp[i - c] + dp[i]) % MOD

print(dp[x])

复杂度：时间 O(n × x)，空间 O(x)。

有序 vs 无序的区别：

遍历顺序	结果	说明
先金额 for i in range(x) → 后硬币	有序	每种组合按顺序计数多次
先硬币 for c in coins → 后金额	无序	每种组合只计数一次

例题 7：Minimizing Coins（完全背包求最少件数）

来源：CSES - Minimizing Coins

给定 n 种硬币价值 $c_i$，求凑成金额 x 所需的最少硬币数（每种无限件）；无法凑成输出 -1。

限制：$1 \le n \le 100$，$1 \le x \le 10^6$，$1 \le c_i \le 10^6$。

思路：最少件数完全背包。dp[j] 为凑成 j 的最少硬币数，dp[0] = 0、其余 INF，转移 $dp[j] = \min(dp[j - c_i] + 1)$。

INF = 10 ** 18
n, x = map(int, input().split())
coins = list(map(int, input().split()))

dp = [INF] * (x + 1)
dp[0] = 0

for c in coins:
    for i in range(c, x + 1):
        dp[i] = min(dp[i], dp[i - c] + 1)

print(dp[x] if dp[x] != INF else -1)

复杂度：时间 O(n × x)，空间 O(x)。