刷题刷到 CodeForces 808E Selling Souvenirs 的时候，我第一反应是“这不就是个 01 背包吗”，再一看数据范围，直接就清醒了。n 和容量都是 10^5 量级，物品重量只有 1、2、3 三种，价值却可以很大。这题明面上叫“超大01背包”，实际上考的是对背包问题结构的理解：重量种类极少，能不能把普通背包的状态压缩到极致？这篇文章就围绕这个题，把我从“想到贪心”到“写出三分搜索”再到“处理各种边界”的完整过程拆开讲，适合刚学完背包、第一次遇到大容量背包题目的选手参考。
1. 这题的第一反应，和常规背包的死刑判决
1.1 题目到底在问什么
题目本身非常朴素：有 n 件纪念品，每件物品重量是 1、2、3 中的一个，价值是给定的正整数，背包容量是 m，问能装下的最大总价值是多少。关键限制是 n 和 m 都可以到 10^5。代码量很小，但思路如果不转变，基本是死路。
我第一次看到这种题，脑子里立刻浮出标准 01 背包的转移方程：
dp[j] = max(dp[j], dp[j - w] + v)
但这次不行，因为容量是 10^5，常规二维 DP 要开 n 乘 m 的表格，也就是 10^10 个状态，空间和时间都爆炸。
1.2 为什么直接上二维 DP 必死
假设 n = 10^5，m = 10^5，标准 01 背包需要遍历每个物品，再遍历每个容量，运算量是 10^10 级别。即使把二维优化成一维滚动数组，时间也完全不可接受。
有人会说“那就用压位、用 bitset 优化”，但这里物品有价值，不是简单的存在性问题，bitset 只能处理能不能凑出某个容量，没法直接求最大价值。这条路也走不通。
1.3 为什么纯贪心也会翻车
既然重量只有三种，很多人会立刻想到按性价比排序：算一算每个物品的单位重量价值，从高到低拿。这个思路听起来合理，但背包问题里贪心几乎都是错的，这题也不例外。
举一个反例：容量是 3，有重量 1 价值 2 的物品，也有重量 3 价值 5 的物品。按单位价值排序，重量 1 的物品单位价值是 2，重量 3 的物品单位价值约 1.67，贪心会先拿重量 1，然后剩下容量 2，再也放不下重量 3，最终价值只有 2。但显然直接拿那个重量 3 价值 5 的物品才是最优的。
贪心失败的关键在于：重量 3 的物品会一次性占掉三个容量，如果只看单位价值，它往往被低估，因为容量余量没办法被零散利用。
2. 把重量卡进 {1,2,3}：这个约束才是真正的入口
2.1 按重量分组是第一步
这题破局的核心是“重量种类极少”。既然只有三种重量，那就把物品分成三组：
- 重量为 1 的物品
- 重量为 2 的物品
- 重量为 3 的物品
每组内部按价值从大到小排序，然后做前缀和。
- pref1[i] 表示重量为 1 的物品中，取价值最高的 i 件的总价值
- pref2[j] 表示重量为 2 的物品中，取价值最高的 j 件的总价值
- pref3[k] 表示重量为 3 的物品中，取价值最高的 k 件的总价值
这个分组的意义是把“选哪些”变成“选几个”。因为同一重量的物品内部，最优选择一定是优先拿价值高的，所以取前 k 个就是最佳方案。
2.2 前缀和数组：把“选几个”变成 O(1) 查询
有了分组和排序，后续所有计算都不需要再关心具体是哪件物品，只需要知道“我打算拿几个重量为 2 的”，然后用 pref2 直接拿到最优价值。
这个技巧在背包问题的很多变体里都通用。只要重量种类少，就可以把同重量的物品看成一整块来处理。前缀和本身也帮我们避开了“逐个枚举物品”的高复杂度，是整道题能不能从 O(n*m) 降到 O(m log m) 的关键。
2.3 重量 3 的枚举：把三维降成二维
重量 3 的物品是三种里面最特殊的，它会一次占用三个容量。但换个角度想：既然它占容量大，那它的数量在答案里不会太多，因为背包容量被总量限制住了。
具体做法是枚举最终方案里拿多少个重量 3 的物品：
for k in 0..min(cnt3, m / 3): ans = max(ans, pref3[k] + solve(m - 3 * k))
这里 cnt3 是重量 3 的物品数量。每枚举一个 k，剩下的问题就变成：容量为 m - 3k，只能用重量 1 和重量 2 装，求最大价值。
这个过程把三维问题降成了二维，而且枚举量是 O(cnt3) 级别，完全可以接受。
3. 剩余容量里的 1 和 2：为啥不能直接贪心，却能三分
3.1 固定 x 个重量 2 之后的问题
现在问题变成了：给定容量 r，有重量 1 和重量 2 两组物品，怎么取最大价值？
如果只取一种重量，直接贪心就行。但两种重量混合，贪心会出错，原因其实和原来的问题一模一样：重量 2 会占据两个单位容量，如果剩余容量是奇数，多出来的那一个单位只能留给重量 1。
所以很自然的想法是枚举“拿几个重量 2 的物品”。假设最终拿了 x 个重量 2 的物品，那么剩余容量 r - 2x 可以全部用来放重量 1 的物品。于是局部价值：
val(x) = pref2[x] + pref1[r - 2x]
这个式子很直观，但 x 的取值范围最大也能到 r/2，如果每个 k 都枚举所有 x，复杂度又会变成 O(cnt3 * r)，还是会超时。
能不能不用枚举 x，而是直接找到 val(x) 的最大值？
3.2 val(x) 是凹函数：三分合法的依据
答案是肯定的，因为 val(x) 是一个凹函数。
简单解释一下：pref2[x] 是凹函数，因为重量 2 的物品按价值降序排列，每多拿一件，新增的价值会越来越小。pref1[r - 2x] 看成 x 的函数时，也是凹函数，因为 x 每增大一点，能拿的重量 1 数量就少一点，而重量 1 的价值也是递减的。两个凹函数相加仍然是凹函数。
凹函数的特点是“先上升，后下降”，最多有一个峰值区域。这就意味着可以用三分搜索在 O(log r) 的时间内找到最大值。
3.3 三分实现与边界暴力兜底
三分搜索本身很简单，但实现时有一个关键细节：凹函数可能存在很长一段平台，也就是连续几个 x 的 val 都相等。三分在平台上可能会陷入死循环或者跳错方向。
我的处理办法是：三分到区间长度小于等于 3 就停，然后对剩下的几个点暴力枚举取最大值。这样即使前面三分的收缩方向判断有点小问题，最后几格暴力也能兜住。
代码逻辑大概是：
while (R - L > 3) { int m1 = L + (R - L) / 3; int m2 = R - (R - L) / 3; if (val(m1) < val(m2)) L = m1; else R = m2; } for (int x = L; x <= R; ++x) best = max(best, val(x));
这里注意 val(m1) 和 val(m2) 相等时，我把右边界往左收，也可以把左边界往右收，但因为最后暴力枚举了小区间，所以对正确性没有影响。
4. 完整代码和每一段的为什么
4.1 读入与分组排序
先看完整实现，所有关键步骤都加了注释。
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<ll> pref1, pref2, pref3; ll val(int x, int r) { // 拿 x 个重量为 2 的物品时，剩余容量全部用来拿重量为 1 的物品 int rem = r - 2 * x; if (rem < 0) return 0; int take1 = min((int)pref1.size() - 1, rem); return pref2[x] + pref1[take1]; } ll getBest(int r) { if (r <= 0) return 0; int max2 = min((int)pref2.size() - 1, r / 2); int L = 0, R = max2; while (R - L > 3) { int m1 = L + (R - L) / 3; int m2 = R - (R - L) / 3; if (val(m1, r) < val(m2, r)) L = m1; else R = m2; } ll best = 0; for (int x = L; x <= R; ++x) { best = max(best, val(x, r)); } return best; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<ll> v1, v2, v3; for (int i = 0; i < n; ++i) { int w; ll v; cin >> w >> v; if (w == 1) v1.push_back(v); else if (w == 2) v2.push_back(v); else v3.push_back(v); } auto buildPref = [&](vector<ll> &a) { sort(a.begin(), a.end(), greater<ll>()); vector<ll> pref(a.size() + 1, 0); for (int i = 0; i < (int)a.size(); ++i) { pref[i + 1] = pref[i] + a[i]; } return pref; }; pref1 = buildPref(v1); pref2 = buildPref(v2); pref3 = buildPref(v3); ll ans = 0; int max3 = min((int)v3.size(), m / 3); for (int k = 0; k <= max3; ++k) { ll cur = pref3[k] + getBest(m - 3 * k); ans = max(ans, cur); } cout << ans << "\n"; return 0; }4.2 getBest 函数：重量 1 和 2 的局部最优
getBest 接收的是“只剩重量 1 和 2 可用时的背包容量 r”。它内部通过三分找最优的“拿几个重量 2”。
有几个地方必须留意。
一是 r / 2 的上限。x 不能超过容量的一半，因为每个重量 2 的物品占 2 个容量。
二是 rem 超过重量 1 物品总数的情况。比如容量有 100，但重量 1 的物品总共只有 30 个，那么 rem 可能算出来是 80，实际只能拿 30 个。用 min(pref1.size() - 1, rem) 就是为了防止越界。
三是如果物品价值出现负数。这题正常数据是正整数，但在一些改编题里可能给负价值。排序的时候应该先把非正价值的物品直接剔除，或者对前缀和做一次“只保留正收益前缀”的处理。否则负物品会让 pref 不是最优前缀，三分求出来也可能不是真正的最优。
4.3 主循环：枚举重量 3 的数量
主循环的 k 枚举所有可能拿的重量 3 数量。pref3[k] 是拿 k 个重量 3 的最大价值，getBest(m - 3 * k) 是在剩余容量下拿重量 1 和 2 的最大价值。
这里有个容易被忽略的点：即使物品的价值都是正数，k 也不是越多越好。因为重量 3 的物品虽然单件价值高，但它会占用更多容量，可能导致重量 1、2 的高性价比物品放不下，所以必须每个 k 都试一遍。
时间复杂度是 O(cnt3 * log cnt2)，cnt3 最多 10^5，log 级别是 17 左右，运算量完全够跑。
5. 这题最容易翻车的三个细节
5.1 平台段毁三分的惨案
三分最典型的翻车不是方向判断错，而是凹函数中间有平台。当 val(m1) 和 val(m2) 相等时，如果直接把左边界 l 跳到 m1，可能把真正的最优峰值跳过；如果直接跳右边界，也可能跳过。即使函数是凹的，平台也可能和峰值粘在一起。
我一开始只把三分的结束条件写成 R - L > 2，结果在平台很多的数据上答案偶尔差 1。后来改成“缩到长度为 3 后暴力枚举”，这个问题就消失了。这个处理办法在所有三分题里都建议用，非常稳。
5.2 前缀和越界和负值物品
写 getBest 时，最容易犯的错是 pref1[take1] 里的 take1 超过 pref1 的长度。问题出在 rem 很大的时候，比如预算是 10^5，而重量 1 的物品只有 100 个，直接取 pref1[100000] 就会越界。
解决方法是取 min(cnt1, rem)。另一个容易踩的是负价值物品：如果价值可以为负，贪心排序取前 k 个可能把负的也纳进来，但最优解一定不会拿负价值的东西。稳妥做法是分组后先过滤 v <= 0 的物品，或者在前缀和构建后额外取一个“前缀最大值”来兜底。
5.3 对拍验证：不知道对不对时就这样确认
我写完这题以后，总觉得三分和枚举 k 的组合有点玄，于是写了一个暴力程序对拍。暴力就是最普通的 DP，设 n 很小、容量很小，比如 n 不超过 20，容量不超过 200，然后随机生成大量数据，比对两份程序的输出。
对拍结果确实出现过差异。后来查出来是因为我的 val 函数里 rem 算成负数时处理不当，导致 x 取到不合法值后 pref 越界。这个坑靠肉眼很难看出来，但对拍一下立刻就能暴露。
建议做这类思维比较绕的题目时，先写一个暴力 DP 对拍程序，再优化成三分版本，心里会踏实很多。对拍脚本逻辑很简单：同样的随机输入，跑两个程序，比较输出是否一致，不一致就停下调试。
6. 做完之后的延伸：同款套路还能打哪些题
6.1 重量种类少的大背包变体
这题的套路本质上是一个更通用的思想：当物品重量种类特别少时，可以对其中某一种重量做枚举，剩下的转化为更简单的问题。
“重量种类少”是这类超大背包题目的灵魂。以后看到重量只有 1 和 2，或者重量只有 1、2、3 的题目，都可以考虑分组排序、前缀和、枚举+三分这套组合。比如某些背包题限制了物品重量只能是某个小质数集合，也能用类似方法。
6.2 和多重背包二进制拆分思路的区别
有一定基础的朋友可能会想到多重背包的二进制拆分，但这两个思路完全不同。多重背包的二进制拆分是为了把一个物品拆成若干个 01 物品，本质还是在做标准背包；而这题是从重量种类入手，直接把标准背包状态压缩掉，核心是把价值函数变成凹函数再用三分。
6.3 我个人的做题体会
这道题给我最大的启发是：遇到看似是大背包的题，先别急着写 DP，而是先观察物品有什么特殊性质。重量只有三种就是最明显的信号，顺着它分组、排序、前缀和，思路一下就顺了。另外就是三分这类数值搜索一定要配一个暴力枚举尾部区间，甚至配一个暴力对拍，这是我在几次三分翻车后学会的最值钱的一课。
如果你在比赛里遇到这题，我的建议是：先花五分钟确认是不是标准背包，是的话果断放弃二维 DP，直接往重量种类少的方向想。把重量 3 枚举完，再对重量 1、2 做三分，思路清晰，代码也不长，现场写起来比临时想其他优化要稳得多。
