最近有朋友在准备华为OD机考问到一道双机位C卷里出镜率很高的动态规划题——MELON的难题。这题从名字到内容都很有意思表面是个“分瓜”问题实际上考的是01背包的经典变体。网上搜到的题解大多只给一种语言但机考现场你根本不知道IDE里默认打开的是Java还是C更别说有人习惯用Python、JS、Go甚至纯C来写。所以我专门把这题的思路完整拆了一遍再把Java、Python、JS、GO、C、C六种常见解法全部过了一遍整理成这篇笔记。无论你是刚准备刷题的小白还是已经在牛客网刷了不少套题的选手这题都值得认真看一遍——它能帮你区分“真会DP”和“背过模板”这两种状态。1. 题目背景双机位C卷里的高频动态规划题1.1 华为OD机考C卷是什么华为OD机考现在普遍要求双机位监考一个摄像头拍脸一个拍桌面和周围环境。这种环境下你没法像平时练习那样切换到别的窗口查API文档也没法翻书去查状态转移方程。所以考场上比的就是“熟练度”——看到题面能不能快速识别出考点、能不能立刻写出核心代码框架。OD机考一般分A卷、B卷、C卷、D卷每套卷子背后是一个题库批次题面会有差异但难度基本保持一致。C卷是其中出题比较稳定的一套动态规划基本是必考章节而MELON的难题恰恰就是DP里最典型的“伪装题”之一。很多第一次见它的人第一反应都是“排序之后贪心一下”结果不是样例过不了就是只过一部分测试点。这题就是用来筛掉那批“只会模板、不会变通”的候选人。1.2 还原题面我看到的版本是这样的MELON有一堆西瓜每个西瓜都有一个正整数重量。他想把这堆西瓜分成两堆使得两堆西瓜的总重量之差尽量小。请你计算并输出这个最小差值。输入描述第一行输入一个整数n表示西瓜数量。第二行输入n个正整数表示每个西瓜的重量。输出描述输出一个整数表示分成两堆后两堆重量差的最小值。这个版本是最常见的也是最适合拿来讲背包思路的。另外机考历史上也出现过“判断能否平分”的变体核心做法一样只是最后多一个判断如果sum - 2 * dp[target] 0说明能均分。理解了基础版变体其实就是顺手的事。1.3 为什么这题值得单独写一篇原因很简单这题的代码量很少但思路转换的跨度很大。它不会直接告诉你“这是一个背包问题”而是把背包藏在了一个生活场景里。你需要自己做一层抽象把“两堆重量差最小”翻译成“从所有西瓜中选出一部分让这一部分的总重量尽量接近总重量的一半”。这个抽象能力恰恰就是机考DP题的核心考察点。你刷了一百道模板题不如把这一题真正吃透。而且这题还有个特点它在六种语言里的写法几乎一样但每个语言的语法细节、数组初始化方式、循环写法都不一样。考场上你用什么语言就得把这个语言的版本写得没有任何卡顿。所以我下面会把六种语言的版本全部铺开逐个拆开讲。2. 解题思路从暴力到01背包的完整推导2.1 暴力枚举为什么不行第一次看到“分成两堆让差最小”最直白的想法是枚举所有分法。假设有n个西瓜每个西瓜要么分到A堆要么分到B堆那一共有2的n次方种组合。这个复杂度在n20的时候就已经是104万n30直接超过10亿机考的时限根本跑不完。如果再往深想一层可能有人会说“那用DFS加剪枝行不行”。确实n比较小的时候DFS可以过但一旦n加到50、100DFS照样爆炸。机考的测评数据不会让人轻易摸到边界它就是要逼你选择一个时间复杂度稳定可控的算法。所以这题的正确方向一定是找多项式时间的解法。而“选一部分物品让总重量尽量接近某个上限”这个描述本身就是01背包的标准场景。2.2 核心转化两堆差最小等于逼近总重量的一半假设所有西瓜的总重量是sum分完两堆之后A堆重量是XB堆重量就是sum-X。两堆的差值是|X - (sum-X)| |2X - sum|。要让这个差值最小本质上就是让X尽量接近sum/2。因为X不可能超过sum/2还比sum/2更优——如果X sum/2那我把A堆和B堆对调一下X就变成sum-X了差值会变更小。所以问题可以转成一句话从n个西瓜中任选若干个让选出来的总重量不超过sum/2的前提下尽量大。到这里这个题已经从“分堆问题”变成了“选物品问题”。而“不超过某个容量选择物品使价值最大”——这不就是01背包的原型吗。2.3 01背包状态定义与转移方程把每个西瓜看成一个物品它的重量是w[i]价值也是w[i]因为这里选得越重越好价值和重量是一样的。背包容量就是target sum/2向下取整。定义dp[j]表示“在容量为j的背包里能装下的最大重量”。初始状态dp[j] 0表示什么都不装的时候重量为0。对于每个西瓜重量w我们考虑要不要把它放进背包不选dp[j]保持不变还是dp[j]。选容量j需要先腾出w的空间所以是dp[j - w] w。两者取最大值dp[j] max(dp[j], dp[j - w] w)这个过程必须保证每个西瓜只能选一次所以内层循环要从大到小遍历j也就是for j target; j w; j--。如果从小到大遍历那么dp[j - w]可能是本轮已经更新过的值一个西瓜就会被重复选中那就变成完全背包了答案必错。等所有西瓜都处理完dp[target]就是“不超过sum/2的最大子集重量”。最小差值就是sum - 2 * dp[target]这个公式几乎可以把正确答案直接算出来所以整个题的代码量才会这么少。2.4 滚动数组和初始化细节二维dp当然也能写dp[i][j]表示前i个西瓜在容量j下的最大重量。但注意到每一轮更新只用到了上一轮的数据所以我们完全可以用一维数组滚动更新空间复杂度从O(n * target)降到O(target)。初始化时dp数组全填0。有些类似的题目会填负无穷那是因为要求“恰好装满背包”而这个题要求的是“不超过容量的最大重量”用0初始化没有任何问题。填负无穷反而会出错。另外要注意target的取值。sum为偶数时target sum/2如果dp[target]恰好等于target差值就是0说明能完美平分。sum为奇数时target向下取整两堆无法完全相等但最小差值也一定能通过公式算出来不需要额外特判。3. 多语言代码实现Java / Python / JS / GO / C / C3.1 Java实现与拆解import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] weights new int[n]; int total 0; for (int i 0; i n; i) { weights[i] sc.nextInt(); total weights[i]; } int target total / 2; int[] dp new int[target 1]; for (int w : weights) { for (int j target; j w; j--) { dp[j] Math.max(dp[j], dp[j - w] w); } } System.out.println(total - 2 * dp[target]); } }Java版需要注意两点。第一Scanner读取大量数据时性能一般但这题的数据量通常不大不会成为瓶颈如果真遇到超大输入建议换成BufferedReader。第二dp数组的大小是target 1target由total除以2得到所以数组大小是运行时动态的这在Java里没问题。实际考场上我建议直接用int[] dp new int[target 1]别为了省空间搞什么花活。3.2 Python实现与拆解def main(): n int(input()) weights list(map(int, input().split())) total sum(weights) target total // 2 dp [0] * (target 1) for w in weights: for j in range(target, w - 1, -1): if dp[j - w] w dp[j]: dp[j] dp[j - w] w print(total - 2 * dp[target]) if __name__ __main__: main()Python写这题最舒服因为列表生成式[0] * (target 1)直接搞定初始化。内层循环用range(target, w - 1, -1)实现从大到小遍历注意第二个参数是w - 1不是w因为range的结束位置是开区间。有些Python选手习惯用input().split()直接读整行但如果你不确定第一行和第二行之间有没有空行、第二行数据会不会被拆成多行更稳妥的写法是用sys.stdin.read()一次性读取所有内容再解析。我平时刷题为了省事直接readlines读进来再split一次能避免很多输入格式的坑。Python版跑这题的效率完全够用不用担心性能。3.3 JavaScript实现与拆解const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let lines []; rl.on(line, (line) { lines.push(line); }); rl.on(close, () { const n parseInt(lines[0], 10); const weights lines[1].split( ).map(Number); const total weights.reduce((acc, cur) acc cur, 0); const target Math.floor(total / 2); const dp new Array(target 1).fill(0); for (const w of weights) { for (let j target; j w; j--) { dp[j] Math.max(dp[j], dp[j - w] w); } } console.log(total - 2 * dp[target]); });Node.js环境里最麻烦的就是输入输出。机考时的JS环境通常就是Node.js所以必须用readline模块。这里我用了最稳妥的累积lines再统一处理的方式。有几个坑提前说第一parseInt(lines[0], 10)的第二个参数10一定要写不然遇到前导零的字符串会解析出问题第二reduce算总和时如果数组元素是字符串会变成字符串拼接所以要先map(Number)转换第三new Array(target 1).fill(0)比循环赋值更快但fill在有些老版本Node里也支持不用担心兼容性。还有一个细节JS的数组长度如果是0比如target为0new Array(1).fill(0)也能正常工作所以不会越界。整体逻辑和Java版完全一致只要熟悉readline模板考场写起来很顺。3.4 Go实现与拆解package main import ( bufio fmt os ) func main() { in : bufio.NewReader(os.Stdin) var n int fmt.Fscan(in, n) weights : make([]int, n) total : 0 for i : 0; i n; i { fmt.Fscan(in, weights[i]) total weights[i] } target : total / 2 dp : make([]int, target1) for _, w : range weights { for j : target; j w; j-- { if dp[j-w]w dp[j] { dp[j] dp[j-w] w } } } fmt.Println(total - 2*dp[target]) }Go版本的特色是fmt.Fscan能自动跳过换行和空格所以读取整数非常干净。但要注意缓冲区问题数据量大的时候fmt.Fscan性能会拉胯所以这里用了bufio.NewReader包一层。实测下来OD机考的数据量用bufio完全够稳。Go的make([]int, target1)会把所有元素初始化为0这一步天然符合需求。内层循环里我没用Go内置的max函数——实际上旧版Go没有max新版Go 1.21之后才加了内置max。为了保证在各种编译环境都能过直接用if判断更稳妥。这也是Go刷题的一个关键点不要依赖太新的语法特性。3.5 C实现与拆解#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint weights(n); int total 0; for (int i 0; i n; i) { cin weights[i]; total weights[i]; } int target total / 2; vectorint dp(target 1, 0); for (int w : weights) { for (int j target; j w; j--) { dp[j] max(dp[j], dp[j - w] w); } } cout total - 2 * dp[target] endl; return 0; }C版本的代码和Java几乎一模一样因为两者语法相近。这里用vector而不是裸数组好处是自动管理内存、初始化为0也方便。要特别注意dp[j] max(dp[j], dp[j - w] w)这一行如果j从大到小遍历dp[j-w]一定是上一轮的旧值这是整个滚动数组算法的核心。还有一个隐藏问题如果target特别大比如total能达到10万甚至100万vector分配内存会比较大但在OJ上通常限制内存所以不要盲目开太大。题目如果把数据范围定在100以内dp数组最多几千完全够用。C跑这种题在六种语言里性能最好基本不用担心超时。3.6 C实现与拆解#include stdio.h int main() { int n; scanf(%d, n); int weights[1005]; int total 0; for (int i 0; i n; i) { scanf(%d, weights[i]); total weights[i]; } int target total / 2; int dp[100005] {0}; for (int i 0; i n; i) { int w weights[i]; for (int j target; j w; j--) { int val dp[j - w] w; if (val dp[j]) { dp[j] val; } } } printf(%d\n, total - 2 * dp[target]); return 0; }C版本是六个版本里最“原始”的没有容器、没有自动扩容数组大小必须自己指定。我这里的写法是直接开了两个固定大小的数组weights[1005]和dp[100005]。这是投机取巧的办法假设n不超过1000、总重量不超过10万。真实机考中如果题目明确给了范围就按范围开数组如果没给宁可开大一点也不要越界。有些编译器支持变长数组VLA比如int dp[target 1]但在部分OJ的编译环境下可能报错。最保险的做法还是用一个足够大的常量数组或者用动态内存分配malloc。另外C语言没有max函数所以用if判断来更新dp[j]效果一样。如果你担心重量总和超过10万导致数组越界可以把dp开到更大比如1000005刷题时空间充裕多写几个0没坏处。3.7 六种语言关键差异对照表语言输入读取方式数组初始化倒序遍历写法最大风险点JavaScanner或BufferedReadernew int[target 1] 默认0for (int j target; j w; j--)Scanner大输入性能一般Pythoninput().split()或sys.stdin.read[0] * (target 1)range(target, w - 1, -1)range结束位置容易写错JSreadline模块收集linesnew Array(target1).fill(0)for (let j target; j w; j--)parseInt忘了写进制Gofmt.Fscan bufio.Readermake([]int, target1) 默认0for j : target; j w; j--别依赖新版内置maxCcinvector (target1, 0)for (int j target; j w; j--)vector扩容和内存Cscanf大数组显式赋0或 {0}for (int j target; j w; j--)数组大小越界这张表是我觉得这篇笔记最值钱的部分。你平时看题解每个题解只给你一种语言的代码但只有把所有语言放一起对比你才会发现核心算法完全一样差别全部集中在语法细节上。把这些细节提前踩平考试时才不会因为某个语言特性卡壳。4. 手撕样例与边界情况实测4.1 标准用例推演拿一个简单例子完整走一遍。输入5 2 3 4 5 9总重量total 23target 11。初始化dp数组长度为12全为0。处理重量2容量11到2的每个位置dp[j]都会被更新成能装下的最大重量经过这轮dp[2]2dp[3]2一直到dp[11]2。处理重量3dp[5]5dp[6]5dp[11]更新为523。处理重量4dp[6]可以从dp[2]46得到更新dp[9]变成9dp[11]变成94239或者426取大的。处理重量5dp[7]变成7dp[10]变成10dp[11]可以从dp[6]511所以dp[11]11。处理重量9dp[11]可以从dp[2]911依然是11不变。最终dp[11]11答案23 - 2*11 1。也就是说一堆取2、4、5重量为11另一堆取3、9重量为12两堆差1这就是最优解。4.2 容易踩的边界场景第一个边界是n等于1。比如输入1\n7total7target3dp[3]0答案7。这意味着两堆只能分出一个7和空堆差值就是7。如果题目隐含要求“两堆都非空”这种case就有点尴尬。机考里通常要么n2要么允许空堆但保险起见你可以思考一下自己的解法在n1时输出是否合理。第二个边界是所有重量相等的情况。比如四个3total12target6dp[6]6答案0完美两堆。这里没问题。第三个边界是总重量为奇数。比如重量是1、2、4total7target3。dp能装下不超过3的最大子集是312答案7-61。这表示两堆重量分别为3和4差1已经是最优了。代码不需要特判奇数直接算就行。第四个边界是单个西瓜重量超过target。比如n2重量5和100total105target52。处理重量5时更新dp[5]5处理重量100时内层循环j从52开始j100不成立所以根本不执行dp[52]还是5。答案105-1095也就是一堆5、另一堆100差95。这个场景验证了内层循环条件j w的重要性当单个物品重量大于背包容量时它没法被放进背包循环条件直接跳过它逻辑完全正确。4.3 一组对比测试结果输入totaltargetdp[target]输出2, 3, 4, 5, 923111111, 2, 3, 4105505, 100105525953, 3, 3, 3126601, 1, 1, 1, 1, 712660最后一行手动解释一下一堆取1、1、1、1、1重量为5另一堆取7差是2。但dp[6]6说明有办法凑出6取111111不成立因为没有第六个1。实际上dp[6]6怎么来的是取7不可能76。哦这组数据有误我重新算一下如果输入是五个1和一个7total12dp[6]最大是5答案12-102。但实际上有没有办法让dp[6]67装不下6五个1只能凑到5所以dp[6]5答案2。如果要让输出为0应该改成六个1total6target3dp[3]3答案0。所以上表最后一行需要修正为输入1 1 1 1 1 1输出0。这种小插曲也提醒我们测试样例一定要亲手验证不能想当然。5. 备考实战中的常见问题与避坑技巧5.1 读题习惯先判断是DP还是贪心这题最大的坑就是容易让人用贪心思路把重量排序然后每次把当前最大的瓜放到重量小的那堆里。这种策略在很多普通数据上看起来合理但样例一复杂就会翻车。比如重量1、1、2、2、3、5贪心会怎么放排序后依次分配最后可能得到差值2但DP能得到差值012361258不对11226358差2但其实1561236差值0这组数据就能说明问题用另一种组合方式。我给你的建议是刷到这种“选一部分、求最接近某个值”的题直接默认它是背包问题不要浪费时间证明贪心策略。考场上时间宝贵与其纠结不如直接写标准DP模板。证明留给赛后复盘做。5.2 代码细节输入格式的坑我见过不少同学在输入上翻车。第一种情况是第二行的重量可能有多个空格甚至换行后继续给数字第二种情况是n后面可能没有换行直接跟空格。Java的Scanner、Go的fmt.Fscan、C的cin都能自动跳过空白字符问题不大。Python如果只用input().split()读一行遇到换行就会漏数据。JS的readline会把每行当成一个事件所以用拼接lines再split的方式最稳。如果真的想一劳永逸建议每种语言都准备一套“万能输入模板”比如Python用data list(map(int, sys.stdin.read().split()))然后从data[0]取n再从data[1:]取重量数组。这样无论输入怎么换行都能一次性解析完。5.3 双机位考试环境下的应试建议双机位监考意味着你的摄像头范围覆盖桌面手机必须放在远处IDE不能联网。这种环境下最实用的备考策略就是“把模板刻进肌肉记忆”。比如JS的readline模板、Go的bufio模板、Java的Scanner模板考前一定要单独练几遍确保不假思索就能写出来。另外机考环境一般不允许你用在线编译器本地IDE也没有代码补全插件所以不要依赖IDE的自动补全。数组初始化、循环怎么写、常用内置函数叫什么都要做到闭着眼能写。像这道题的倒序遍历很多人平时写习惯了正向遍历考场上脑子一热就写成for j w; j target; j结果变成完全背包样例全错。这种低级失误在双机位压力下特别容易犯唯一的预防方法就是多练。5.4 常见问题速查表问题现象可能原因解决办法答案偏大但不是大得离谱用了贪心思路做分堆改为01背包求最大子集和答案偏小甚至出现负值内层循环正向遍历物品被重复选把j从target向下遍历到wdp数组越界target1分配太小或数组下标负数确认j w数组大小为target1输出0但实际不能均分把奇数总重量误判为能均分用sum % 2先判断或直接用公式sum - 2*dp[target]Python读取输入时数据缺失用input()只读了一行重量跨行了改用sys.stdin.read()一次性读取C语言跑起来崩溃固定数组开小了按题目最大范围开大数组或使用malloc这张表覆盖了我自己刷题和帮别人看代码时遇到的绝大多数问题。尤其是“答案偏小”那条几乎每个初学者都栽过。倒序遍历这个知识点你说它简单确实就是一行代码的事但如果你不理解为什么倒序考场上稍微一紧张就会写反。6. 我自己刷这题的体会最后聊点题外话。我第一次见MELON的难题是在准备机考的冲刺阶段当时已经刷了不少动态规划题觉得自己挺稳的。结果看到“分成两堆重量差最小”第一反应竟然是“这不就是排序后贪心吗”然后样例验证了一下感觉没问题直到交上去发现只能过60%的测试点。那时候我才意识到背了那么多模板遇到实际问题还是容易被表面现象带偏。后来我把这题当作案例反复琢磨才真正理解了“把问题转化成背包”这个过程的价值。它不只是一个题而是一类题的入口从“划分成两个集合使差值最小”到“选一部分尽量接近总和的一半”这个抽象过程在机考里反复出现。可以说MELON的难题就是一个打开背包问题大门的钥匙。如果你正在准备OD机考我建议你把这题至少手写三遍第一遍看着题解写第二遍合上书自己写第三遍用至少两种语言写。写完这题再把力扣的“分割等和子集”、“最后一块石头的重量 II”刷掉你会发现自己对背包问题的理解瞬间提升一个档次。三遍之后再回想第一次见到这题时那个纠结的自己大概会忍不住笑出来。