题目描述
每次拿两块相撞(剩下重量差)，求最后剩下的最小重量。
stones = [2, 1, 4]
总和/目标 = 7 / 3
输出 = 1
思路解析
设一堆和为 s，另一堆为 total−s，差 = |total−2s|。s 越接近 total/2 差越小。这就变成 0-1 背包了：在容量 total//2 里，子集和最大能到多少。
建表 · dp[0]=0：dp[j] 表示容量 j 内能装出的最大子集和。容量上限 = 7//2 = 3。先全初始成 0。
用石头 2：放石头 2（从大到小更新）：dp[3]=2、dp[2]=2。容量 2、3 都能装出和 2。
用石头 1：放石头 1：dp[3]=max(2, 2+1)=3、dp[1]=1。现在容量 3 能装出和 3（就是 2+1）。
石头 4 > 3 · 跳过：石头 4 超过容量 3，装不下。最大一堆和 dp[3] = 3。
算答案：一堆 3、另一堆 7−3=4，差 = 4−3 = 1。也就是 total − 2×dp[3] = 1。
以后遇到「把数组分两堆让差最小」，一律转成背包：在 sum/2 容量里求最大子集和，差 = sum − 2×它。和目标和、分割等和子集是同源的。
参考代码（Python）
Python
1total = sum(stones); target = total // 2
2dp = [0] * (target + 1)
3for s in stones:
4 for j in range(target, s - 1, -1): # 0-1: 从大到小
5 dp[j] = max(dp[j], dp[j - s] + s) # 尽量装满
6return total - 2 * dp[target]复杂度分析
- 时间复杂度：O(n × sum) —— n 块 × 半和
- 空间复杂度：O(sum) —— 一维 dp
套路模板
记住这个骨架：容量取半和、0-1 背包求最大子集和、答案= 总和−2×它。凡是「让两部分尽量接近」的题，都套这个。
Python
1target = sum(a) // 2
2dp = [0] * (target + 1)
3for x in a:
4 for j in range(target, x - 1, -1): # 0-1 从大到小
5 dp[j] = max(dp[j], dp[j - x] + x)
6return sum(a) - 2 * dp[target]易错点
- ❌ 容量取 total → ✅ 取 total // 2（只需逼近一半，取整个和是浪费且会错）
- ❌ 内层从小到大 → ✅ 0-1 背包从大到小（每块石头只能用一次）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。