分割礼单

核心缓存区的第八层，是Zero的礼物仓库。无数包装精美的礼盒堆成小山，每个盒子上都标着重量。

"要分成两堆。"Echo说，"两个人抬，重量差越小越省力。"

"这就像……"CC想了想，"像分赃。"

"不是分赃。"你说，"是平衡。"

"平衡？"

"对。"你说，"把所有礼物分成两半，让两边重量尽量接近。这样两个人都不会太累。"

CC看着那堆礼物，忽然笑了——不是平时的那种笑，是一种带着疲惫的、但真诚的笑容。

"你分得公平点。"她说，"不然我揍你。"

"放心。"你说，"用最少的差值。"

你开始写。把礼物分成两半——前半部分列举所有可能的组合重量，存进一个集合；后半部分也列举所有组合，对每种组合在前半部分的集合里找最接近的值。最后算出最小的差值。

屏幕上跳出了结果。最小差值：1。

"差1。"你说，"几乎完全公平。"

"1。"CC说，"就像我和你。差一点点，但差不多。"

Echo的投影闪烁了一下。她没有说话。

礼物在屏幕上被分成两堆，一堆由你抬，一堆由CC抬。Echo飘在最上面，像一面旗帜。

"走。"她说，"核心就在前面。"

题目描述

$n$ 件礼物，每件有重量 $w_i$。把礼物分成两堆，使得两堆重量之差的绝对值最小。求这个最小差值。

输入格式

$n$。然后 $n$ 个整数表示重量。

输出格式

最小差值。

输入样例

3 5
1 2 3

输出样例

3

提示

• 双向搜索 / 折半枚举（Meet-in-the-Middle）。
• 把物品分成两半，分别枚举子集和。
• 对前半部分的所有和排序，后半部分每个和在排序数组中二分找最接近的值。
• 时间复杂度 $O(2^{n/2} \log 2^{n/2})$。

寻找最短路径

八道门，全部打开。

核心缓存区的尽头，是一扇巨大的青铜门。门上刻着一行字："你已学会寻找最短路径。现在，进入更深的搜索世界。"

"下一章。"Echo说，"是启发式搜索。"

"启发式搜索？"CC问。她的声音已经恢复如初——那个皮厚、嘴硬、不怕死的CC回来了。

"给搜索加上直觉。"Echo说，"不光盲目地找，还要猜哪个方向更有可能通向答案。"

"这像……"CC想了想，"像打猎。不光追着跑，还要猜猎物往哪边逃。"

"对。"Echo说，"不算糊涂账。"

CC看了你一眼，嘴角微微上扬。

"走。"她说，"去算一笔大账。"

[下一章：动态规划 —— 核心缓存区深处]