02_Knapsack DP 背包DP

背包 DP

背包问题简介

背包问题通常涉及将有限容量的容器用物品的子集填满，我们希望计算或优化与物品相关的某些数量。几乎每次，你可以将每个物品视为具有正重量，而我们选择的物品的总重量不得超过容器的容量，这个容量是一个数字。

背包问题的变体

• 0/1 背包问题: 选择物品的子集，使得它们总价值最大化，且总重量不超过容器容量
• 完全背包问题: 找到所有可能的、由任何物品子集实现的总重量，这些总重量不超过容器容量
• 计数问题: 计算有多少种物品序列能够完全填满容器，这意味着总重量正好等于容器的容量（顺序可能重要也可能不重要）

提示: 背包问题的动态规划解法通常包含一个状态来跟踪背包的容量，状态转移涉及尝试将一个物品添加到背包中。在竞赛编程中，你可以预期经典背包问题会被赋予变化、伪装和额外的状态信息。

---

多重背包问题

问题描述

有 N 种物品，每种物品有重量 w_i、价值 v_i 和数量 c_i，求在不超过背包容量 W 的情况下，选择物品使得总价值最大。

解法

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

初始条件：dp[j] = 0

状态转移：将数量 c_i 拆分成 1, 2, 4, 8, … 的物品件数，转化为 0/1 背包问题

dp[j] = max (dp[j], dp[j − w] + v)

代码实现

# 多重背包 - 二进制优化
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))
        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])

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

---

总结

问题类型	状态转移	内层循环方向
0/01 背包	dp[j] = max (dp[j], dp[j − w] + v)	倒序
完全背包	dp[j] = max (dp[j], dp[j − w] + v)	正序
多重背包	二进制优化转为 0/01 背包	倒序