P3010 Dividing the Gold 题解：0/1背包转换与方案数DP详解-北京尧图网络

出门前还在想“今晚把这题刷完就睡”结果一道[USACO11JAN] Dividing the Gold S让我折腾到凌晨。这题在洛谷是P3010USACO 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总重量S18target9。按贪心思路模拟6放进第一堆第一堆变成6第二堆05放进第二堆因为第二堆更轻第二堆变成54放进第一堆第一堆变成103放进第二堆第二堆变成8。最后两堆重量是10和8差2。但实际上最优分法是36给一个人45给另一个人两边都是9差值0。贪心在这道题上就是错的。原因很本质这是一个0/1背包问题每个金块只有“选”和“不选”两种状态互相影响贪心的局部最优没法保证全局最优。一旦你意识到要用背包后面就顺了。2. 状态设计和方案计数最容易出错的三个细节2.1 可达性数组与倒序更新核心数据结构是两个数组ok[j]布尔值表示能否从若干金块中凑出总重量jcnt[j]整数表示凑出总重量j的方案数。初始状态都只有j0是可达的凑出0的方案数为1。每来一块重量为w的金子我们就从target开始倒着更新到w。为什么必须倒序这是0/1背包的经典规则倒序能保证每个物品只被使用一次。举个例子假设当前只有一个重量为5的金块正序更新会发生什么从0到target遍历j当j5时ok[5]变成1继续往后遍历当j10时由于ok[5]已经为1ok[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 完整代码下面这段代码是我实际调试后能稳定通过的一版C17包含注释。注意我这里先按“不取模、使用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; vectorint w(n); int sum 0; for (int i 0; i n; i) { cin w[i]; sum w[i]; } int target sum / 2; vectorchar ok(target 1, 0); vectorlong 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 自测用例与期望输出本地调试时我习惯多跑几组数据这里列出几组有代表性的输入targetbestdiffcnt[best]说明3个金块3 5 46521总重12凑5是一边的重量4个金块3 4 5 6990236和45两种完美平分2个金块3 33302两个相同金块算两种方案5个金块1 1 1 1 33315凑3有4种三块1和1种单独31个金块73071只有一块时只能一边拿7另一边空以第4组为例总重量是7target3best3diff1。方案数5是怎么来的选三个重量1C(4,3)4种选一个重量31种。所以cnt[3]5完全符合手算。代码的时间和空间复杂度也很清晰最坏情况每个金块都要扫一遍0到target总复杂度O(n * sum / 2)空间O(sum / 2)。SUM不大的时候完全没问题这也是P3010这类Silver题敢用背包的原因。4. 提交后容易踩的坑和验证思路4.1 N1时差值和方案数的语义先看一个极端情况只有一块金子重量比如是7。总和是7target3能凑出的最大不超过3的重量是0所以best0diff7cnt[0]1。这意味着什么呢一边拿7另一边拿0。如果题目允许“有一边为空”这个结果是合理的。但有些题面会默认“分成两堆”时每堆都必须非空那N1就是非法情况或者答案需要特殊处理。我建议写代码前先看题面有没有“non-empty”之类的限制。USACO这类题一般不会把空堆当成问题毕竟人家问的是“分给两个人”其中一个人一个子都没拿到也是分法。但要是你参加的比赛中明确说了每堆都必须有金子那N1的时候要单独特判。4.2 数组越界与循环条件一个低级的坑是循环边界。target可能比某个w[i]小比如只有一个金块重量7的情况target3。这时for (int j target; j w[i]; --j)根本不会执行因为37不成立。另一种错误写法是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到target3j3ok[0]1cnt[3]cnt[0]变成1。处理第二个3时还是正序j3ok[0]1cnt[3]cnt[0]变成2。j6因为target是3根本没这个位置所以没影响。看起来[3,3]在target3下正序也能得2问题不大。但如果target更大比如总重量为10target5输入两个5正序就会出大问题。处理第一个5时j5可达处理第二个5正序到j5继续加然后j10也会假设能用同一个5凑出10实际target5看不见j10所以也不行。为了暴露问题换一个场景只有一块金子重量5target10。正序更新时j5达到j10也会因为ok[5]变成可达而被更新成可达于是best会变成10diff0。可你手里只有一块5不可能凑出10。这就是为什么倒序是原则性要求不是随便写写。5. 从P3010延伸总重量很大时还能怎么做5.1 Meet in the Middle总重量大的时候的替代方案背包DP的前提是target不能太大。如果总重量达到10^9甚至更大数组直接开不下那就要换思路。n比较小比如n40的时候可以用meet in the middle。把金块分成前后两半每半最多2^n/2个子集分别枚举出所有子集和。然后让后一半的所有子集和排好序对前一半的每一个和a二分查找一个b让ab尽量接近target同时不超过target。这样复杂度大约是O(2^(n/2) * log(2^(n/2)))对于n40大概是一百万级别的枚举加排序完全可行。方案数怎么数如果你只是求最小差值不用统计方案数那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”这种老题吃透后面遇到任何“背包凑半值”的变体都能秒转换。希望这篇记录能帮你少走我走过的弯路。

P3010 Dividing the Gold 题解：0/1背包转换与方案数DP详解

相关推荐

Pi 1.0 发布：原生MCP与Durable如何重塑终端编程代理

程序员水会生存指南：把无效会议变成高效时间管理

PyTorch张量操作精讲：索引分片、合并与维度调整

更多资讯

领域特定评估实战：用 Argilla、Distilabel 与 LightEval 构建考试问答评估流水线（smol-course）

Apache Storm 集群安全加固实战：从 OS 层防护到 Kerberos 认证与 ACL 授权

CMake FindOpenCL 模块全解析：从 find_package 到 OpenCL::OpenCL 导入目标

YOLO船舶检测实战：数据集解析与训练避坑指南

题解：洛谷 P14361 [CSP-S 2025] 社团招新

U-Boot Kbuild深度解析：从零构建RV1106移植的四大核心步骤

今日更新

PHP htmlentities()函数用法讲解

AI Agent工程实战：从七要素到七个决策点的系统设计指南

AI入局芯片设计验证：验证收敛50倍加速的真相与应对

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？