一维 0-1 背包 DP：倒序枚举容量，保证每件物品至多选一次，O(nm) 求出不超过背包容量的最大价值。
OJ: roj
题目 ID: 1294
难度:入门
标签:动态规划0-1 背包一维 DP
创建: 2026-09-30 03:39
更新: 2026-10-05 08:18
后置题目
roj 20008唱KB 的选歌环节直接套用 A 教的倒序枚举容量的一维 0-1 背包骨架，把「每件物品至多选一次」迁移成「每首歌至多唱一次」，只是在同一转移上把状态由最大价值换成恰好总长 s 的最多首数，再叠加首数优先的字典序比较。roj 2041usaco-3.1.2 总分A 教的一维背包 f[v] 状态与转移被 B 完整沿用，B 只把 A 的倒序改成容量维正序，从而由 0-1 选取变为可重复选取的完全背包。roj 2033usaco-2.3.4 货币系统B 的组合计数沿用 A 教的一维滚动数组状态设计与「枚举方向决定物品能否重复取用」这一步：A 用倒序枚举容量保证每件至多选一次，B 把同一 ways 数组改为按面值外层、金额内层正序枚举（main.py 的 ways[amount] += ways[amount - coin]），使 ways[j-c] 含本轮值从而面值可重复取用，B 原文也直接以 0/1 背包倒序扫描作对照；在此之上 B 才叠加按面值分组去重、max 换成方案数累加与 ways[0]=1 边界。roj 1299糖果A 教的「一维 dp 表上逐件物品做每件只用一次的 0/1 转移」正是 B 的每一轮循环：B 只把状态维从容量换成模 K 的余数，并用旧表快照代替倒序枚举来维持 0/1 语义，再叠加同余数取最大总和与答案取 dp[0] 的建模。roj 1272【例9.16】分组背包B 的分组背包直接沿用 A 教的「一维 f[v] + 倒序枚举容量避免物品重复叠加」这一步，只在其外再套一层枚举组的循环luogu P1757通天之分组背包B 的分组背包正是把 A 教的倒序枚举容量 01 转移原样搬进组内层，只把外层从物品换成组来叠加组内互斥约束luogu B4141[信息与未来 2016] 素数分解B 的素数分解正解直接复用 A 教的那一步——一维背包倒序枚举容量保证每件物品只用一次，代码 for(j=n;j>=p;j--) dp[j]=max(dp[j],dp[j-p]+1) 就是 A 的 f[v]=max(f[v],f[v-w]+c)；B 只是把物品换成筛出的素数（重量 p、价值 +1）并额外叠加埃氏筛与 dp 初值 -1 的恰好装满处理，A 入门、B 普及-，属台阶式前置。luogu P1466[USACO2.2] 集合 Subset SumsB 原样复用 A 教的『倒序枚举容量保证每件物品只用一次』这一步（B 代码 for j=target..i 倒序），只把取 max 价值换成方案数累加，再叠加 A 未教的奇数判 0 与除 2 去重。luogu P18025 倍经验日B 在 main.cpp 中每个好友都先加 lose_i 再倒序枚举药水量 j 做转移，直接复用 A 教的「依次处理每件物品并倒序枚举容量」的一维 0-1 背包步骤，只是把 A 的 max(f[v],f[v-w]+c) 改成 max(dp[j]+lose_i,dp[j-use_i]+win_i)，倒序枚举保证每个好友最多只打一次。luogu U661994疯狂的背包问题(12) - 二维费用问题B 把 A 教的『倒序枚举容量保证每件物品只选一次』原样扩成二维费用背包的两维倒序枚举，转移式只是在一维 0-1 背包基础上加一个费用维luogu U661992疯狂的背包问题(8) - 多重背包问题 IB 的多重背包正解（main.cpp 第 21 行 for (int c = V; c >= 0; --c) 内套 k 循环）原样复用 A 教的『倒序枚举容量保证每件物品至多选一次』这一步，只把每件物品换成展平后的 s_i 个 01 副本并在内层叠加件数枚举，B 文中也明说与标准 01 背包的倒序要求完全一样。luogu U663298疯狂的背包问题(3) - 01背包问题（计数组合问题）B 的 dp[c] 状态定义与「倒序枚举容量保证每件只用一次」这一步直接照搬 A 的 0-1 背包一维写法（代码里同为 for(c=V;c>=v;--c)），只在 dp[0]=1 初始化、加法累加与取模上把求最大价值换成计数恰好装满的方案数。luogu U663710疯狂的背包问题(6) - 完全背包问题（计数组合问题）B 沿用 A 教的一维 dp[c] 容量状态骨架与「枚举方向决定物品复用次数」这一具体判定，把 A 的倒序翻转成正序，使 dp[c-v] 含当前物品贡献从而实现无限件，再把 A 的 max 转移换成 dp[c]+=dp[c-v] 的组合计数（dp[0]=1、取模）并叠加先物品后容量的组合语义去重。luogu P2392kkksc03 考前临时抱佛脚B 的正式解 main.cpp 在 subject_time 里逐题倒序枚举时间 j，直接复用 A 教的「倒序枚举容量保证每件物品只用一次」这一步，只把 max 取最大价值换成 dp 可达标记；B 的新难度在互补子集归约到 total/2。luogu P2904[USACO08MAR] River Crossing SB 的一维容量 dp 结构与 A 教的「用 dp 按容量归并选择、做 max 背包转移」是同一步，只是把物品固定成一趟运 k 头、max 换 min；但 A 只教到 0-1 背包的倒序枚举（每件至多一次），B 的真实难度之一「重复使用故为完全背包（正序枚举）」正是 A 未教的相反规则，A 的这一步在 B 中只是骨架，因此属模板级复用。luogu P2946[USACO09MAR] Cow Frisbee Team SB 直接沿用 A 教的『一维数组按累积量作下标、每件物品只用一次的 0/1 转移』这一步（B 原文也明确把一头奶牛看成一个只能选一次的物品），只把容量下标换成余数下标、把 max 换成方案数累加，再叠加取模与空集去重，难度从 入门 升到 普及-，台阶性成立。luogu P1679神奇的四次方数B 把 A 教的容量维枚举方向判定反用：由 A 的倒序改为正序枚举，使 dp[j-w] 取到本轮已更新值，从而让每个四次方数无限复用，再叠加 min 项数与 INF 初始化。luogu P2430严酷的训练B 的 main.cpp 第 34-36 行原样复用 A 教的容量倒序枚举转移，只把容量换成时间、物品换成题目，A 未涉及的是耗时按水平倍率换算的建模环节luogu P1164小 A 点菜B 的计数 0/1 背包（main.cpp:24 注释“倒序枚举金额，保证每种菜最多只选一次”）原样沿用 A 教的倒序枚举保证物品至多选一次这一步，只把转移由 max 换成 dp[j]+=dp[j-a[i]]、dp[0] 由 0 改成 1，在同一骨架上叠加“恰好花完”的计数语义
题目描述
有 4 6 / 1 4 / 2 6 / 3 12 / 2 7 → 23。
思路
经典 0-1 背包。设
参考代码
Python 版：
python
#!/usr/bin/env python3
# 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-09-30 03:43
# update_at: 2026-09-30 03:43
import sys
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
f = [0] * (m + 1) # f[v]：重量不超过 v 的最大价值
for _ in range(n):
w, c = next(data), next(data) # 每件物品（重量，价值）
for v in range(m, w - 1, -1): # 倒序枚举容量，每件至多选一次
f[v] = max(f[v], f[v - w] + c)
print(f[m])
if __name__ == "__main__":
solve()C++ 版（同一算法）：
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-10-05 08:18
* update_at: 2026-10-05 08:18
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXM = 12880 + 5; // 背包容量上限 + 1
ll n, m;
ll f[MAXM]; // f[v]：重量不超过 v 时能获得的最大价值
void solve() {
cin >> n >> m;
for (ll i = 1; i <= n; i++) {
ll w, c;
cin >> w >> c;
// 倒序枚举容量，保证每件物品至多选一次
for (ll v = m; v >= w; v--) {
if (f[v] < f[v - w] + c) {
f[v] = f[v - w] + c;
}
}
}
cout << f[m] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}