疯狂的背包问题(1) - 01背包问题

GitHub跳转原题关系图返回列表

使用01背包DP，dp[c]表示容量c时的最大总价值，容量倒序枚举确保每件物品只选一次；同模型的 Python 写法因 3 MB 内存限制必然 MLE。

OJ: luogu

题目 ID: U661986

难度:入门

标签:动态规划01背包背包

创建: 2026-08-08 23:11

更新: 2026-09-14 07:09

后置题目
roj 20008唱KB 先把唱K化成容量 t-1 的 0/1 背包，其第三步「每首歌要么选要么不选、从大到小逆序更新」正是 A 教的「倒序枚举容量保证每件物品只选一次」这一步，只是把 dp 的最大价值换成 f 的最多首数并叠加首数优先的字典序比较。roj 2041usaco-3.1.2 总分B 的完全背包完全沿用 A 教的一维转移式 dp[t]=max(dp[t],dp[t-t_i]+p_i) 与「扫描方向决定件数」这一步，只是把 A 的容量倒序（每件只选一次）换成正序（种类可重复选），并在此之上叠加按耗时升序处理与被支配种类剪枝。roj 2033usaco-2.3.4 货币系统B 的完全背包计数沿用 A 教的一维滚动数组状态设计并把扫描方向规则翻转使用：A 用倒序让 dp[c-v] 保持上轮值以保证每件物品只选一次，B 在 main.py 里用正序让 ways[j-c] 含本轮值，从而同一面值可重复取用，B 原文也直接以倒序 0/1 背包作对照说明这一分界；在此之上 B 才叠加按面值分组去重、max 换成方案数累加与 ways[0]=1 边界。roj 1299糖果B 把 A 教的「同一状态只保留最优值、每件物品只选一次」照搬到一维 0/1 背包上：dp[j] 同样只留最优总和并用旧表做一次取/不取转移（代码 old[from]+value 更新 dp[j]），只是把状态从容量换成总和模 K 的余数，并叠加环形回绕 (j - r + k) % k。roj 1272【例9.16】分组背包B 直接复用 A 教的容量倒序枚举，把倒序读旧值的性质从「每件物品只选一次」推广到「每组最多选一件，同组物品不叠加」。roj 1266【例9.10】机器分配B 的分组背包沿用 A 教的「相同容量只保留最大价值」这一最优子结构，把一维容量 dp 扩成前 i 组恰好分 j 台的二维 dp，再叠加 res 记决策回溯luogu P1757通天之分组背包B 明说自己是“在 01 背包的基础上加一层组的约束”，复用 A 教的容量倒序枚举来保证一件物品不被重复选，只是把外层循环从“物品”换成“组”，用同一轮 dp 快照实现组内互斥。luogu B4141[信息与未来 2016] 素数分解B 直接把 A 教的『容量倒序枚举保证物品只选一次』当成 0/1 背包骨架，套在素数集合上（重量 p、价值 +1、目标和恰好为 n），再做埃氏筛与恰好装满的不可达初始化luogu P1466[USACO2.2] 集合 Subset SumsB 的 main.cpp 原样复用 A 教的『容量倒序枚举保证每件物品只选一次』这一 0/1 背包骨架，只把转移从取 max 价值换成方案数累加 dp[j]+=dp[j-i]，再叠加总和为奇数判 0 与除以 2 去重两个 A 未教的新步骤。luogu P18025 倍经验日B 的解法主体就是 A 教的容量倒序枚举，并原样搬用「倒序枚举使 dp[j-use_i] 保留上一轮旧值、从而保证每件物品只选一次」这一理由（原文：这保证了每个好友最多只打一次），只在其上叠加不打也有 lose_i 的保底收益。luogu U661994疯狂的背包问题(12) - 二维费用问题A 教的『容量倒序枚举保证每件物品只选一次』被 B 直接用作二维费用背包的两维倒序循环（B 的 main.cpp 中 j、k 两层均倒序，并注明“这和 01 背包倒序的道理完全一样”），B 只在此基础上叠加 A 未涉及的第二个费用维；难度由入门升到普及-，台阶性与方向均成立。luogu U661992疯狂的背包问题(8) - 多重背包问题 IB 把每种物品的 s_i 件展平成多个 01 物品后，仍沿用 A 教的『容量倒序枚举保证每件物品只选一次』（main.cpp 第 21 行 for (int c = V; c >= 0; --c)），只是在倒序容量循环内层再枚举选取件数 k，属于在 01 背包模板上叠加一层枚举。luogu U663298疯狂的背包问题(3) - 01背包问题（计数组合问题）B 直接沿用 A 教的 01 背包一维 dp[c] 状态与容量倒序枚举（main.cpp 里同一层 `for (c = V; c >= v; --c)` 只把 max 换成加法累加），仅在 dp[0]=1 初始化与取模上把「求最大价值」改成「计数方案数」。luogu U663710疯狂的背包问题(6) - 完全背包问题（计数组合问题）B 直接沿用 A 的一维容量 dp 与「枚举方向决定物品复用次数」这一步：A 用倒序保证物品只用一次，B 反过来用正序枚举容量，让 dp[c-v] 被当前物品反复更新，从而把同一状态骨架改成完全背包的组合计数。luogu P2392kkksc03 考前临时抱佛脚B 的正式解 main.cpp（28-31 行）把每道题当体积、逆序枚举时间做 dp[j] |= dp[j-times[i]]，直接沿用 A 教的『容量倒序枚举保证每件物品只用一次』这一步，只把求最大价值换成可达性标记；B 新增的难度是用互补子集性质把分组化归为不超过 total/2 的子集和。luogu P2904[USACO08MAR] River Crossing SB 的完全背包主循环直接沿用 A 的按容量维度一维 dp 转移结构，只把 max 改 min、把物品重量换成趟次 k，A 只教到 01 背包（倒序，见 problems/luogu/U661986/index.md:59-61），可重复使用物品、预处理 trip_cost[k] 以及最后减 M 都是 A 未涉及的新增内容，属模板级复用luogu P2946[USACO09MAR] Cow Frisbee Team SB 直接复用 A 教的『只保留最优状态、不关心前面具体选了哪些物品』这一最优子结构观察，把它从背包切容量视角迁移成按余数设状态的 01 计数 DP。luogu P1679神奇的四次方数B 直接复用 A 讲透的「一维 dp 容量维枚举方向决定物品使用次数」这一判定：A 用倒序保证每件只选一次，B 的完全背包把同一容量维转移改成正序让 dp[j-w] 用本轮新值以实现无限复用，再叠加 min 项数目标、INF 初始化与四次方数枚举。luogu P2430严酷的训练B 的 main.cpp 第 34-36 行直接套用 A 教的『容量倒序枚举保证每件物品只选一次』这一步，只把容量维换成时间维 t、物品换成题目；B 额外叠加的、A 完全未涉及的是把知识点耗时乘水平倍率换算成 cost[i] 的物品建模环节，难度由 入门 升到 普及-，台阶性与方向都成立。luogu P1164小 A 点菜B 的 main.cpp:23-27（以及 main-rainboy.cpp:25-31、main.py:7-9）原样复用 A 教的『容量倒序枚举保证每件物品只选一次』这一步，只把转移从 max(dp[c],dp[c-v]+w) 换成 dp[j]+=dp[j-price]、初始化 dp[0] 从 0 改成 1，得到恰好花完 M 元的方案数；B 原文也明确以“和求最大价值的 01 背包比”为起点，属于在同一 0/1 背包骨架上叠加计数语义，难度从 入门 升到 普及-，台阶性成立。luogu P2725[USACO3.1] 邮票 StampsA 教的一维背包状态设计（dp[容量] 只留最优值、dp[x-v]+代价 转移、按枚举方向控制物品可用次数）正是 B 完全背包解法的第一步：B 把它换成 min 与 +1 求每个面值的最少邮票数，再叠加扫描最长连续前缀这一新步骤。luogu P1832A+B Problem（再升级）B 直接沿用 A 的“外层枚举物品、内层枚举容量”一维 dp 状态设计，只把 A 的 max 转移改成正序累加，并借用 A 的“枚举顺序决定物品能否重复使用”这一结论说明正序让素数可重复选，属于在同一背包模板上叠加素数筛与组合计数流程。luogu P2834纸币问题 3B 的 main.cpp:25-27 把 A:62 讲透的『容量枚举方向决定物品能否重复使用』这一步反向为正序枚举（j 从 a[i] 到 w），用同一维 dp 数组实现纸币无限张；台阶是 A 未教的组合计数语义与先纸币后金额的循环顺序辨析。luogu P2840纸币问题 2B 的 main.cpp:25-31 沿用 A 教的一维容量 dp 骨架与「容量枚举方向决定物品能否重复使用」这一判定，只是把 A 的倒序枚举反向改成正序（A:62 说正序会让同一物品被选两次，B:59 说先枚举纸币正序会把顺序合并成组合），从而换成完全背包排列计数 dp[j]=(dp[j]+dp[j-a_i])%MOD，并额外叠加 A 未讲的取模与排列/组合循环顺序辨析；难度从 入门 升到 普及-，台阶性成立。luogu U663733疯狂的背包问题(7) - 完全背包问题（计数排列问题）B 的 main.cpp:25-30 逐行复用 A 教的『一维 dp[c] 由 dp[c-v] 转移＝再放入一件物品 v』这一步，只把 A 的 max 取最优值与容量倒序换成计数累加与容量正序，叠加 A 未涉及的排列/组合枚举顺序判别；A 入门、B 普及-，落差 1 级，台阶性成立。luogu P1048[NOIP 2005 普及组] 采药B 的正式主解解法二（main.cpp 第 24-27 行 for(t=total_time;t>=need_time[i];t--) dp[t]=max(dp[t],dp[t-need_time[i]]+herb_value[i])）逐字复用 A 教的『容量倒序枚举保证每件物品只选一次』这一步 0/1 背包转移，只把 A 的体积维换成采药的时间维、物品价值换成草药价值，额外叠加的是 A 未涉及的自顶向下记忆化搜索写法作为对照；难度从 入门 升到 普及-，台阶性成立。

目录

  1. 题意
  2. 思路
  3. 代码
    1. 复杂度
    2. 总结

    题意

    N 件物品，每件只能选一次。第 i 件体积 v_i，价值 w_i。背包容量 V。挑选一些物品使总体积不超过 V 且总价值最大，输出最大价值。

    思路

    一句话本质：每件物品只能选或不选，容量有限制，问最大总价值。

    为什么不能直接枚举所有选法？

    brute.py 用位掩码枚举了 2^N 种选法，每次检查总体积并更新最优价值。N 最大到 1000，2^1000 是天文数字，根本无法跑完。

    既然不能全枚举，我们如何逐步处理这些物品？

    可以把物品一个一个地拿出来决策。每处理一件物品，我们只面临两个选择：选它或不选它。

    选或不选这个物品，影响了什么？

    选了它就占了容量、增加了价值；不选就什么也不变。也就是说，当我们处理到第 i 个物品时，唯一需要关心的状态是"目前已经占用了多少容量"。

    如果有多种方式占用相同的容量，我们只需要保留哪一种？

    只保留总价值最大的那种。因为后续物品只关心剩余容量还有多少，不关心前面具体选了哪些物品。不同路径到达相同容量，价值更大的那条路径永远更优。这正是 DP 的核心——最优子结构。

    状态定义和转移是什么？

    定义 dp[c] 表示占用容量 c 时能获得的最大价值。

    初始 dp[0] = 0，其他为 0（一件都不选时价值为 0）。

    对于每件物品 (v, w)，考虑容量 c 从 V 到 v 倒序：

    text
    dp[c] = max(dp[c], dp[c - v] + w)

    含义：要么不选（保持 dp[c]），要么选（从 c-v 转移来，加上价值 w）。

    为什么容量必须倒序枚举？

    因为每件物品只能选一次。如果正序枚举，处理小的 c 时更新了 dp[c]，后面更大的 c’ = c + v 再次用到 dp[c] 时会包含这件物品的影响，等于同一件物品被选了两次。倒序能保证 dp[c - v] 是"没选过当前物品"时的状态。

    代码

    C++17 正解

    cpp
    /**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:11
 * update_at: 2026-08-08 23:11
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 1);
    for (int i = 0; i < N; ++i) {
        int v, w;
        cin >> v >> w;
        for (int c = V; c >= v; --c)
            dp[c] = max(dp[c], dp[c - v] + w);
    }
    cout << dp[V] << '\n';
    return 0;
}

    Python 版本（会超内存）

    python
    import sys

def ints():
    for x in sys.stdin.buffer.read().split():
        yield int(x)

it = ints()
n = next(it)
C = next(it)
f = [0] * (C + 1)

for _ in range(n):
    vol = next(it)
    val = next(it)
    if vol > C:
        continue
    for c in range(C, vol - 1, -1):
        f[c] = f[c] if f[c] >= f[c - vol] + val else f[c - vol] + val

print(f[C])

    main.py 的状态定义和倒序转移与 C++ 完全一致，样例输出 8，随机对拍 300 组也与 brute.py 一致，本机最大数据（N=V=103N = V = 10^3）耗时约 0.1s。但本题内存限制只有 3 MB（3072 KB），而 CPython 解释器本身的常驻内存就接近 10 MB，实测这份代码的峰值 RSS 约 9948 KB——还没算上 f 数组就已经超出限制。因此它在洛谷上必然 MLE，这里只作为 Python 写法对照，正式提交请使用 main.cpp。

    复杂度

    • 时间：O(N × V)，每件物品遍历 V 个容量
    • 空间：O(V)，dp 数组大小 V+1
    • main.py 的时间与空间复杂度相同，但解释器运行时开销约 10 MB，超过本题 3 MB 的内存限制，无法通过。

    总结

    01 背包的核心是每件物品只能选一次，通过容量倒序枚举来保证。dp[c] 记录容量 c 下的最优价值，转移时取"不选"和"选"的最大值。