企业官网建设流程全解析

最近刷 NSUOJ 的时候碰到了 3188 这道题，题名叫“小P的暑假工”。第一眼看到这个名字，以为是个模拟题或者贪心题，毕竟暑假工安排听上去挺像排班表的。结果点进去读了一遍题，背包问题，而且不是普通的 01 背包也不是完全背包，是典型的多重背包。

这道题数据范围设置得挺有讲究，如果你只会暴力拆分，大概率是会超时的。但只要你把多重背包的二进制优化吃透了，代码也就二十来行，非常适合拿来当多重背包的入门训练题。这篇文章我就以 NSUOJ 3188 为例，把从题目建模、状态定义、三种解法到最终的 AC 代码和踩坑记录全部捋一遍。不论你是刚学背包问题的新手，还是准备复习多重背包的选手，这篇应该都能给你一点实在的东西。

1. 题目建模：小P的暑假工到底在考什么

1.1 从故事背景到背包模型

先说一下题目大意。小P放暑假想打工赚钱，他面前有若干种工作，每种工作都有一个“做一次要花多少天”的耗时，也有一个“做一次能赚多少钱”的收益，而且每种工作不是想做多少次就做多少次，数量是有限制的。小P暑假一共有 T 天，问他在这些限制下最多能赚多少钱。

题意听起来很生活化，但剥掉故事外壳之后，它就是一个标准的多重背包模型。我们把“工作的种类”看成物品的“种类”，把“做一次这个工作需要的时间”看成这个物品的“体积”，把“做一次赚的钱”看成物品的“价值”，把“这个工作最多能做多少次”看成物品的“数量上限”，最后把“暑假总天数 T”看成背包的“容量”。

所以问题就变成了：有 N 种物品，第 i 种物品的体积是 w[i]，价值是 v[i]，数量上限是 c[i]，现在有一个容量为 T 的背包，问能装下的最大价值是多少。

这里我强烈建议刚开始学背包的同学，每做一道背包题，都先动手把题目里的故事要素和背包模型里的要素做一次映射。我接触过不少选手，做多了之后拿到题直接套模板，结果题目一变就翻车，根源就在于没有真正理解这个映射关系。

1.2 为什么是多重背包而不是 01 背包或完全背包

很多新手在判断背包类型的时候会犹豫：这个工作能做多次，那不就是完全背包吗？答案是不一定。完全背包要求每种物品可以取无限次，但题目明确说了每种工作有数量限制，这就是“有限次数”，和完全背包的“无限次数”有本质区别。

我们可以用一个直白的类比：01 背包是“一个物品选或不选”，完全背包是“一个物品你可以拿无限个”，多重背包则是“一个物品你可以拿若干个，但最多不能超过某个数”。暑假工这个场景天然就是多重背包，因为现实中一份工作不可能让你无限做下去，要么岗位有限，要么时间有限。

还有一个判断技巧，就是看数据范围。如果一道题数据量很大，而且题目里有“最多可以做 c 次”“库存有限”“某种物品限购”这类关键词，九成就是多重背包。反过来，如果题目说的是“不限次数”“任意多个”，那才是完全背包的范畴。

2. 从暴力到优化：多重背包的三种经典解法

2.1 暴力拆解法：正确但会超时的方案

先讲最朴素的做法。既然第 i 种物品最多能拿 c[i] 个，那我直接在状态转移的时候枚举拿几个不就行了？

我们定义 dp[j] 表示“总耗时为 j 天时能获得的最大收益”。第 i 种工作做 k 次需要耗时 k * w[i] 天，收益是 k * v[i]，那么状态转移就是：

dp[j] = max(dp[j - k * w[i]] + k * v[i])，其中 0 <= k * w[i] <= j，且 k <= c[i]

写出来是三重循环，外层枚举物品种类，中层枚举背包容量，内层枚举拿的数量：

for (int i = 0; i < N; i++) { for (int j = T; j >= 0; j--) { for (int k = 0; k <= c[i] && k * w[i] <= j; k++) { dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]); } } }

这种做法逻辑上没有任何问题，答案一定是正确的。但它的时间复杂度是 O(N * T * C)，如果 N、T、C 稍微大一点，比如都到 1000，那就是十亿次运算，直接超时没商量。

我第一次做多重背包的时候就是先写了暴力版本，样例过了，心里美滋滋，结果一交，TLE，绿色变红色，瞬间清醒。所以暴力拆解只能用来验算思路，不能直接作为正式提交方案。

2.2 二进制优化：把多重背包拆成 01 背包

既然暴力枚举数量不行，那我们换个思路：能不能把多重背包转换成我们已经很熟练的 01 背包？

直接拆肯定是拆不了的，因为每种物品有 c[i] 个，你拆成 c[i] 个独立的物品，物品总数会非常大，复杂度还是 O(N * T * C)。这时候就要用到二进制优化的核心思想：一个数 c，可以用若干个 2 的幂次组合出来。

具体来说，我们把数量 c 拆成几个部分：1、2、4、8、……一直拆到不能再拆为止，最后如果还剩一个余数 r，就再把 r 单独作为一组。举个例子，假设 c = 13，那么 13 = 1 + 2 + 4 + 6，拆出来的组数只有 4 个，比直接拆成 13 个物品少得多。

为什么这样拆不会丢状态？因为任何 0 到 13 之间的整数，都能用 1、2、4、6 这四组数中的若干组拼出来。比如 5 = 1 + 4，7 = 1 + 6，9 = 1 + 2 + 6，全部都能表示。也就是说，我原来枚举 k 从 0 到 13 的所有取法，用这 4 组物品做 01 背包，同样能覆盖所有可能取的数量。

代码实现也很简单：

int cnt = c[i]; for (int k = 1; cnt > 0; k <<= 1) { int take = min(k, cnt); items.push_back({w[i] * take, v[i] * take}); cnt -= take; }

这段代码里的 take 就是当前这一组物品对应的“数量”，把原物品复制 take 份，合成一个新的物品。最后 items 里存的就是所有拆出来的新物品。拆完之后，整个问题就变成了纯 01 背包，再用一维滚动数组逆序遍历容量即可。

二进制优化后，每个物品被拆成了 log(c[i]) 个，总物品数是所有 log(c[i]) 之和，时间复杂度降到 O(N * T * logC)。在 N、T、C 都是 1000 的情况下，一千万次左右，完全够用。

这里再强调一下：为什么不是用十进制拆而是用二进制拆？因为二进制拆分能够以 log 级别的最少组数覆盖 0 到 c 的所有整数，这是信息论层面的最优方案之一。你如果拆成 1、2、3、4、5……那总组数还是 O(c)，没有优化意义。

2.3 进阶方案：单调队列优化

如果你对性能要求更高，多重背包还有更优的解法，那就是单调队列优化，时间复杂度可以做到 O(N * T)。

单调队列优化的核心思路是把容量 j 按照 j mod w[i] 分成若干组，每一组内部用单调队列维护一个滑动窗口最大值。因为 dp[j] 只会从同一组的 dp[j - k * w[i]] 转移过来，所以每一组是独立的，可以用队列优化。

不过说实话，在绝大多数比赛里，二进制优化已经足够应付多重背包了。单调队列优化理解起来门槛更高，代码也更长，属于“听过就行，需要时再补”的知识点。我建议新手先掌握二进制优化，把 3188 这题 AC，然后再去研究单调队列，学习曲线会更舒服。

3. 完整 AC 代码与核心实现细节

3.1 二进制优化版本的 AC 代码

下面给出我提交通过的完整代码，题目是多组输入，所以外层套了一个 while(cin >> n >> T)。

#include <bits/stdc++.h> using namespace std; const int MAXT = 1005; int dp[MAXT]; struct Item { int w, v; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, T; while (cin >> n >> T) { vector<Item> items; for (int i = 0; i < n; i++) { int w, v, c; cin >> w >> v >> c; int cnt = c; for (int k = 1; cnt > 0; k <<= 1) { int take = min(k, cnt); items.push_back({w * take, v * take}); cnt -= take; } } memset(dp, 0, sizeof(dp)); for (auto &it : items) { for (int j = T; j >= it.w; j--) { dp[j] = max(dp[j], dp[j - it.w] + it.v); } } cout << dp[T] << '\n'; } return 0; }

提交结果是我预想中的 AC，运行时间也很短。这题的 N、T、C 范围具体是多少我记不太清了，但二进制优化过之后完全不需要担心超时问题。

3.2 一维滚动数组为什么必须逆序遍历

这里的细节很多人容易忽略：拆完物品之后做的是 01 背包，所以容量循环必须从大到小。

原因在于一维数组 dp[j] 在更新时，dp[j - w] 可能已经被同一轮循环更新过。如果从小到大遍历，那么某个物品会被反复使用，这就变成了完全背包。反过来，从大到小遍历，dp[j - w] 还是上一轮的旧值，这个物品就只会被使用一次，符合 01 背包的语义。

我把这个总结成一句话：逆序是 01 背包的标志，顺序是完全背包的标志。看到滚动数组，先问自己当前这个阶段是 01 背包还是完全背包，再决定遍历方向。

另外一个常见问题是：dp 数组初始化成 0 还是负无穷？这取决于题目问的是“不超过容量 T”还是“恰好装满容量 T”。3188 这道题问的是暑假 T 天内最多赚多少钱，做不完 T 天也没关系，所以是不超过，初始化全 0 即可。如果换成“恰好用满 T 天”的变式，就要把 dp[0] 初始化为 0，其余初始化为负无穷，否则你无法区分“凑不齐”和“凑齐了但价值为 0”这两种情况。

4. 现场复盘：几个差点让我 WA 的坑

4.1 二进制拆分时循环变量别被自己改乱

第一次写二进制拆分的时候，我图省事，写了这样一个循环：

for (int k = 1; k <= c; k <<= 1) { items.push_back({w * k, v * k}); }

这个写法看着没什么问题，但实际上它忽略了一个关键点：如果 c = 13，那么 k 会依次取 1、2、4、8，然后循环条件 k <= 13 还会再让 k 变成 16，此时才跳出。看起来好像没错？错在少处理了余数 6。13 被拆成了 1、2、4、8，这四个数能组合出的最大数是 15，超过 13，但中间的 13 本身能表示吗？1 + 4 + 8 = 13，能表示。但这四个数组合起来会覆盖 13 到 15 的范围，出现了超出实际数量的情况，也就是你可能会让某件物品被取 13 件以上，这就不合法了。

所以正确做法必须引入 take 变量，保证每一组拆分出来的数量之和恰好等于 c：

int cnt = c; for (int k = 1; cnt > 0; k <<= 1) { int take = min(k, cnt); items.push_back({w * take, v * take}); cnt -= take; }

每次从 cnt 里减去已经拆掉的部分，最后 cnt 一定是 0。这样拆完后，所有组加起来正好是原数量 c，不会多也不会少。

4.2 多组输入容易忘记重置状态

3188 这题是多组输入，如果你用全局数组存 dp，那么在每组数据开始之前一定要重置 dp 数组。

我一开始没注意，上一组数据的答案残留到了下一组，结果第二组样例的输出直接比正确答案大了一截，找了半天才发现是初始化问题。后来我习惯在每个 while 循环开头都写一句 memset(dp, 0, sizeof(dp))，或者用 fill(dp, dp + T + 1, 0)，再也不会因为这种低级错误浪费调试时间。

另外，用 vector 来存拆分后的物品，每组数据开始前会自动清空，这个设计在写多组数据的题时很省心。如果你开的是定长数组，记得也要用一个计数器来记录当前物品个数，不能直接用全局 n 去遍历。

4.3 大数量下的溢出隐患

这个题如果数量给得特别大，比如 c 达到 1e9，那么 w * c 可能会直接溢出 int。虽然 3188 的数据范围大概率没那么变态，但养成用 long long 的习惯总没有坏处。

我在做其他背包题时曾因为 int 溢出吃过亏，那次是二维费用的多重背包，所有物品加起来的价值和超过了 2^31，结果答案直接变负数，WA 得莫名其妙。从那以后，只要涉及价值或数量的乘法运算，我都会多加一层确认，必要时直接用 long long。

5. 从 3188 延伸出去：多重背包还能怎么变

5.1 加一个“恰好装满”的限定条件

3188 是求不超过 T 天的最大收益，但如果题目改成“小P必须正好干满 T 天”，那处理方式就变了。

做法是初始化 dp[0] = 0，其余 dp[j] = -INF（一个很小的负值），然后转移逻辑不变。因为在转移过程中，只有能恰好装满的容量 j 才会被更新成有效值，凑不齐的状态会一直保持负无穷，最后 dp[T] 如果是负无穷，就说明无解，不然就是恰好装满的最大收益。

我建议你做完这道题后，自己把初始化改一改，多测试几组数据，对比一下“不超过”和“恰好”两种问法在答案上的差异，能加深对背包初始化的理解。

5.2 混合背包：物品数量有无限个也有有限个

有时候题目会同时存在三种物品：有的只能用一次，有的可以用无限次，有的最多只能用 c 次。这种就叫混合背包。

处理思路也不复杂：如果是 01 背包，就按 01 背包做；如果是完全背包，就按完全背包做；如果是多重背包，就先二进制拆分，再按 01 背包做。整体上只需在一个循环里判断类型，分别处理即可。3188 里的多重背包部分，其实就是混合背包中最需要动脑的一个环节。

5.3 多重背包求方案数

如果题目不求最大收益，而是问“有多少种安排工作的方法能赚到某个目标金额”，那就把 dp 数组的含义从“最大价值”改成“方案数”，转移也改成加法。

具体来说，dp[j] += dp[j - k * w[i]]，初始化 dp[0] = 1。注意方案数可能会非常大，题目一般会给一个模数，记得取模。多重背包求方案数的二进制优化思路和普通多重背包一模一样，唯一的区别是 01 背包部分的加法和取模。

6. 写在最后：这道题带给我的经验

NSUOJ 3188 这道题本身不算难，但它把多重背包最核心的几个知识点都串起来了：状态定义、类型判断、二进制优化、滚动数组遍历顺序、初始化细节。我觉得它非常适合拿来当多重背包的入门题，刷完这一道，再去碰别的多重背包题目会顺畅很多。

我个人在给这道题写题解的时候，最大的体会是：背包问题的代码模板固然重要，但比模板更重要的是“判断题型”和“确定转移方向”这两件事。很多选手看到题目就去套模板，结果 01 背包的代码改了改就交上去，遇到多重背包直接 WA。如果你能把题目里的故事准确映射成“每种物品有几个、体积多少、价值多少、背包容积多少”，那这道题你已经做对了一半。

最后再分享一个小技巧：如果你不确定自己的二进制拆分有没有写对，可以在本地输出一下 items 数组里每一组物品的{w, v}，然后手动验算几组数据。比如原物品是 w = 2, v = 3, c = 13，你应该看到拆出来是 {2,3}、{4,6}、{8,12}、{12,18} 这四组，最后一组余数 6 对应的就是 w * 6 和 v * 6。确认拆分没问题之后，剩下的 01 背包部分基本不会出错。刷题这条路，稳扎稳打比什么都重要。