出门前还在想“今晚把这题刷完就睡”，结果一道[USACO11JAN] Dividing the Gold S让我折腾到凌晨。这题在洛谷是P3010，USACO 2011年1月的Silver组题目，表面看就是个“把金子分成两堆让重量差最小”，可实际上它同时考了0/1背包的经典转换、方案数计数、以及边界条件处理。很多新手上去就想贪心或暴力枚举，三天三夜都过不了；而真正理解背包模型后，代码不过四十行。这篇文章就把完整思路、可提交的C++实现，还有我踩过的几个坑一起写出来，适合刚学动态规划、准备信奥普及组到提高组过渡的同学参考。
1. 这题不是简单平分：原题模型与背包化思路
1.1 题面到底在说什么
先交代题目内容。给你N块金子，每块有一个重量w[i]，现在要把这些金子分给两个人，要求两个人分到的总重量之差尽可能小。如果有多种分法能达到这个最小差值，题目还要你输出“一共有多少种分法”。
输入格式很简单：第一行一个整数N，第二行N个整数，表示每块金子的重量。输出也是两个数，第一行是最小重量差，第二行是对应的方案数。
这里有个很容易被忽略的点：题目问的是“重量差最小”而不是“完全平分”。所以哪怕总重量是奇数、或者无论怎么分都没法做到两边一样重，你也得算出差值最小的那种分法，而不是直接放弃。
1.2 目标等价变形：让其中一堆尽量接近总和一半
设所有金子的总重量为S。如果第一个人分到了重量x，那第二个人自然分到S-x，两者的重量差就是：
|S - 2x|
要让这个差的绝对值最小，本质上就是让x尽量接近S/2。
因为两个人在这个问题里是对称的，我们只需要考虑x小于等于S/2的情况。也就是说，问题变成了：
从N块金子中选出一个子集，使得子集总重量尽量接近 floor(S/2)，但不能超过它。
设target = S / 2（向下取整），我们要找一个最大的可达重量best，满足best不超过target。那么答案里的最小差值就是：
diff = S - 2 * best
这一步转化是整个题目的灵魂。很多同学卡住，就是因为还在枚举“第一个人拿哪些、第二个人拿哪些”，实际上只需要关心其中一堆能凑出多少就行，另一堆自动是补集。
1.3 为什么不能靠排序贪心
有人会想：把金子按重量从大到小排序，每次把当前这块放到总重量较小的一堆里，这不就是最优吗？
拿一组数据试试就知道：金子重量为3、4、5、6，总重量S=18，target=9。按贪心思路模拟：
- 6放进第一堆，第一堆变成6，第二堆0；
- 5放进第二堆（因为第二堆更轻），第二堆变成5；
- 4放进第一堆，第一堆变成10；
- 3放进第二堆，第二堆变成8。
最后两堆重量是10和8，差2。
但实际上最优分法是3+6给一个人，4+5给另一个人，两边都是9，差值0。贪心在这道题上就是错的。
原因很本质：这是一个0/1背包问题，每个金块只有“选”和“不选”两种状态，互相影响；贪心的局部最优没法保证全局最优。一旦你意识到要用背包，后面就顺了。
2. 状态设计和方案计数：最容易出错的三个细节
2.1 可达性数组与倒序更新
核心数据结构是两个数组：
- ok[j]：布尔值，表示能否从若干金块中凑出总重量j；
- cnt[j]：整数，表示凑出总重量j的方案数。
初始状态都只有j=0是可达的，凑出0的方案数为1。
每来一块重量为w的金子，我们就从target开始，倒着更新到w。为什么必须倒序？这是0/1背包的经典规则：倒序能保证每个物品只被使用一次。
举个例子，假设当前只有一个重量为5的金块，正序更新会发生什么？
- 从0到target遍历j，当j=5时，ok[5]变成1；
- 继续往后遍历，当j=10时，由于ok[5]已经为1，ok[10]也会变成1。
可你手里明明只有一个5，怎么能凑出10？这就是同一个物品被重复使用了。倒序遍历时，更新ok[j]只会用到j-w这个位置，而j-w小于j，在倒序过程中还没有被当前这块金子更新过，所以不会重复。
方案数数组的更新同理。这一条看起来简单，却是新手最容易写崩的地方。
2.2 方案数是怎么滚出来的
cnt[j]的转移逻辑可以用一句话概括：
如果凑出j-w是有方案的，那么在这些方案的基础上放上这块金子w，就能凑出j。
所以转移是：
cnt[j] += cnt[j - w]
这里有个隐藏细节：为什么不会把同一个方案重复计算多次？
因为我们是按物品一个一个处理的，并且每个物品只会被用来更新一次cnt。倒序保证使用当前物品时，cnt[j-w]还是“不包含当前物品”的方案数。这样组合起来的就是“集合方案”，不是“排列方案”。
比如重量为1的两块金子，我们想凑出重量1。处理第一块时，cnt[1]变成1；处理第二块时，cnt[1]再加一次变成2。这两个方案分别是“选第一块”和“选第二块”。由于两块金子在物理上是不同的对象，所以这就是2种方案，没问题。
2.3 相同重量、不同金块的计数语义
这里得说清楚一个很多人纠结的问题：如果两块金子重量相同，它们算不算不同方案？
实际分配金子时，每块金子是独立物体，哪怕重量一样，也是不同的选择。所以DP按“处理不同下标的金块”来累加方案数，天然就是正确的。比如上面的[1,1]，凑出1就有2种方案，而不是1种。
还有一个更隐蔽的问题：方案数要不要除以2，或者乘以2？
我这里定义的cnt[best]，统计的是“选出一堆重量为best的金块的组合数”。因为best不超过总重量一半，我把这堆看作较小的一堆，另一堆自动取补集。在洛谷/USACO这类题目常见的题解口径里，直接输出cnt[best]就能过。
但如果你手上的题面明确说“两堆人的身份是有区别的”，那最终方案数可能还要再乘以2，因为两个人谁拿较小堆、谁拿较大堆是两种分配。反过来，如果你把“A拿X、B拿Y”和“A拿Y、B拿X”看作同一种划分，并且diff刚好为0，那每个划分会被统计两次，需要除以2。
我建议做题前先想清楚题目里问的“ways”到底区分不区分人。P3010的原题里一般是直接按cnt[best]输出。为了稳妥，你可以本地用极端数据验证一下：输入两个3，代码输出的是2。如果你觉得答案应该是1，那就是题目语义不同，需要除2。
3. 完整可提交的C++代码与逐段说明
3.1 完整代码
下面这段代码是我实际调试后能稳定通过的一版，C++17，包含注释。注意我这里先按“不取模、使用long long”来写，因为很多USACO老题输出的是精确整数；如果你的题目要求方案数取模，把注释里的MOD打开即可。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> w(n); int sum = 0; for (int i = 0; i < n; ++i) { cin >> w[i]; sum += w[i]; } int target = sum / 2; vector<char> ok(target + 1, 0); vector<long long> cnt(target + 1, 0); ok[0] = 1; cnt[0] = 1; for (int i = 0; i < n; ++i) { int wi = w[i]; for (int j = target; j >= wi; --j) { if (!ok[j - wi]) continue; if (!ok[j]) { ok[j] = 1; cnt[j] = cnt[j - wi]; } else { cnt[j] += cnt[j - wi]; } } } int best = target; while (best > 0 && !ok[best]) { --best; } int diff = sum - 2 * best; cout << diff << '\n'; cout << cnt[best] << '\n'; return 0; }3.2 关键代码段拆解
最核心的就是中间的三层结构：
for (int i = 0; i < n; ++i) { int wi = w[i]; for (int j = target; j >= wi; --j) { if (!ok[j - wi]) continue; ... } }先判断j - wi是否可达。如果不可达，说明就算加上当前这块也凑不出j。这里有个小技巧：很多写法会先把ok[j-wi]赋值给ok[j]，但我更习惯先用continue跳过不可达状态，后面再处理，这样可以保证cnt数组里不会混进无效的累加。
当ok[j]为0时，说明之前没有方案能凑出j，那么用cur这块金子是目前唯一能凑出j的方式，直接cnt[j] = cnt[j-wi]。当ok[j]已经是1时，说明之前已经有一些方案能凑出j，现在又发现了新方案，所以cnt[j] += cnt[j-wi]。
为什么这里不会重复计算同一个方案？因为倒序遍历，cnt[j-wi]还停留在“当前物品未使用”的状态。这一点我在前面已经强调过，代码里体现得非常直接。
找最优值的一段：
int best = target; while (best > 0 && !ok[best]) { --best; }这里是从大到小找第一个可达的重量作为best。因为target已经是总和的一半向下取整，我们要的是“不超过target的最大可达重量”，所以第一个碰到的ok[best]就是答案。如果一直没找到，best最终会跌到0，因为ok[0]一定为1。
3.3 自测用例与期望输出
本地调试时我习惯多跑几组数据，这里列出几组有代表性的：
| 输入 | target | best | diff | cnt[best] | 说明 |
|---|---|---|---|---|---|
| 3个金块：3 5 4 | 6 | 5 | 2 | 1 | 总重12，凑5是一边的重量 |
| 4个金块：3 4 5 6 | 9 | 9 | 0 | 2 | 3+6和4+5两种完美平分 |
| 2个金块：3 3 | 3 | 3 | 0 | 2 | 两个相同金块算两种方案 |
| 5个金块：1 1 1 1 3 | 3 | 3 | 1 | 5 | 凑3有4种三块1和1种单独3 |
| 1个金块：7 | 3 | 0 | 7 | 1 | 只有一块时只能一边拿7另一边空 |
以第4组为例，总重量是7，target=3，best=3，diff=1。方案数5是怎么来的？选三个重量1：C(4,3)=4种；选一个重量3：1种。所以cnt[3]=5，完全符合手算。
代码的时间和空间复杂度也很清晰：最坏情况每个金块都要扫一遍0到target，总复杂度O(n * sum / 2)，空间O(sum / 2)。SUM不大的时候完全没问题，这也是P3010这类Silver题敢用背包的原因。
4. 提交后容易踩的坑和验证思路
4.1 N=1时差值和方案数的语义
先看一个极端情况：只有一块金子，重量比如是7。总和是7，target=3，能凑出的最大不超过3的重量是0，所以best=0，diff=7，cnt[0]=1。
这意味着什么呢？一边拿7，另一边拿0。如果题目允许“有一边为空”，这个结果是合理的。但有些题面会默认“分成两堆”时每堆都必须非空，那N=1就是非法情况，或者答案需要特殊处理。
我建议写代码前先看题面有没有“non-empty”之类的限制。USACO这类题一般不会把空堆当成问题，毕竟人家问的是“分给两个人”，其中一个人一个子都没拿到也是分法。但要是你参加的比赛中明确说了每堆都必须有金子，那N=1的时候要单独特判。
4.2 数组越界与循环条件
一个低级的坑是循环边界。target可能比某个w[i]小，比如只有一个金块重量7的情况，target=3。这时for (int j = target; j >= w[i]; --j)根本不会执行，因为3>=7不成立。
另一种错误写法是：
for (int j = target; j >= 0; --j) { if (j >= w[i]) { ... } }这样写本身没错，但每次循环都要判断，而且当j小于w[i]时continue会浪费大量时间。更危险的是有人把j声明成unsigned int，然后写j >= w[i]，当j减到0后继续减会变成很大的数，导致死循环。用int就不会有这个问题。
4.3 方案数精确输出还是取模
这是我在提交前犹豫最久的地方。P3010这道题在洛谷上很多人直接用long long存方案数，也能过，说明官方数据里的方案数没有大到爆掉。但如果你拿这题去扩展，或者自己造了几百个重量为1的金块，C(200,100)级别的方案数早就超出long long了。
如果题目要求取模，改动很简单：定义一个MOD常量，所有对cnt的赋值和累加都改成取模。我在前面给的完整代码保留了没取模的版本，但注释里提醒了这一点。
如果你在比赛中遇到方案数可能巨大的题，第一件事是确认题面有没有“输出对某个数取模的结果”。没有取模要求但你又怕溢出，那就得考虑上高精度或者用__int128。USACO老题通常不会故意卡你这一点，所以不用自己吓自己。
4.4 一个用于验证正确性的暴力工具
DP写完最难确认的就是方案数对不对。我的笨办法是定期写个暴力对拍：
int brute() { int ansDiff = 1e9, ways = 0; for (int mask = 0; mask < (1 << n); ++mask) { int s = 0; for (int i = 0; i < n; ++i) { if (mask >> i & 1) s += w[i]; } int diff = abs(sum - 2 * s); if (diff < ansDiff) { ansDiff = diff; ways = 1; } else if (diff == ansDiff) { ++ways; } } return ways; }n小于等于20的时候，暴力枚举所有子集是可行的。拿它和DP结果对拍几组随机数据，如果完全一致，说明你的方案数转移没写错。这个对拍习惯能帮你节省大量调试时间，尤其是首次写方案数DP的时候。
4.5 正序循环会翻车的实际演示
为了让你更直观地感受到倒序的重要性，我用[3,3]这组数据模拟一下“正序更新”会得到什么。
初始cnt[0]=1。处理第一个3时，正序从0到target=3：
- j=3，ok[0]=1，cnt[3]+=cnt[0]，变成1。 处理第二个3时，还是正序：
- j=3，ok[0]=1，cnt[3]+=cnt[0]，变成2。
- j=6，因为target是3，根本没这个位置，所以没影响。
看起来[3,3]在target=3下正序也能得2？问题不大。但如果target更大，比如总重量为10，target=5，输入两个5，正序就会出大问题。处理第一个5时j=5可达；处理第二个5正序到j=5，继续加；然后j=10也会假设能用同一个5凑出10？实际target=5看不见j=10，所以也不行。
为了暴露问题，换一个场景：只有一块金子重量5，target=10。正序更新时j=5达到，j=10也会因为ok[5]变成可达而被更新成可达，于是best会变成10，diff=0。可你手里只有一块5，不可能凑出10。这就是为什么倒序是原则性要求，不是随便写写。
5. 从P3010延伸：总重量很大时还能怎么做
5.1 Meet in the Middle：总重量大的时候的替代方案
背包DP的前提是target不能太大。如果总重量达到10^9甚至更大，数组直接开不下，那就要换思路。
n比较小（比如n<=40）的时候，可以用meet in the middle。把金块分成前后两半，每半最多2^n/2个子集，分别枚举出所有子集和。然后让后一半的所有子集和排好序，对前一半的每一个和a，二分查找一个b，让a+b尽量接近target，同时不超过target。
这样复杂度大约是O(2^(n/2) * log(2^(n/2)))，对于n=40大概是一百万级别的枚举加排序，完全可行。
方案数怎么数？如果你只是求最小差值，不用统计方案数，那meet in the middle很轻松。但如果还要方案数，就得在二分查找时把跟b一样大的其他值一起算上，再配合计数数组，稍微麻烦一点。不过大部分信奥题考到这里已经够用了。
5.2 同类题目的套路：背包凑半值模型
P3010这个模型非常经典：一堆物品，选一个子集，让子集重量尽量接近总和的一半。很多题都是它的变体。
比如洛谷P1466 Subset Sums，问的是“把1到N分成两组，使两组和相等，共有多少种分法”，本质上就是凑出S/2的方案数，只是权值变成了1,2,...,N。再比如一些“把一队人分成两队，使两队实力最接近”的题，赋值换成数组就一模一样。
甚至“调度问题”里，把若干任务分给两台机器，让两台机器总耗时差最小，也是同一个模型：机器的总耗时就相当于子集重量。这类问题的本质都是0/1背包取半值，你需要会的是那个“差分等价转换”，而不是死记代码模板。
5.3 我自己调试这题的三个经验
最后抖点干货，都是实际操作中摸索出来的。
第一，在调试时把ok和cnt的整个数组打印出来看。每个金块处理一轮之后，打印一次当前“可达重量和对应方案数”的表格。不要只看最终答案，中间状态能帮你快速定位更新顺序的问题。我最初写错就是因为在cnt[j]已经非0时没加else分支，结果方案数被覆盖而不是累加，打印中间状态一眼就能看出来。
第二，处理前先把金块重量从小到大排一遍序，有时候能让DP提前命中target，虽然复杂度量级没变，但常数会小一些。这个优化在n较大时感受比较明显。
第三，如果两个方案数很大，记得先确认题目要不要取模。不要等提交后因为WA才发现自己漏看了“mod 1000000007”这几个字。USACO的题目通常不搞模数，但洛谷上很多扩展题会加，看清题目永远比猜题目靠谱。
刷题刷到凌晨虽然累，但把“Dividing the Gold”这种老题吃透，后面遇到任何“背包凑半值”的变体都能秒转换。希望这篇记录能帮你少走我走过的弯路。
