问题起源

2010年3月，sw2wolf求助高德纳书中一道很普通的题目：
将 $\sqrt{1},\sqrt{2}, \dots, \sqrt{50}$ ( 1 到 50的平方根）分成两组，把每组中的数相加，得出两个数， 然后比较这两个数的差别。
问题： 用常见的计算机语言之一编写一个程序，找出最小的差别的两组， 要求该程序在计算机上运算得出结果所花费的时间不超过10秒。

算法讨论

winxos认为:
$\sqrt{1}+\sqrt{2}+...+\sqrt{50}=239.0358006035207771$, 一半等于 $119.5179003017603885$,
问题变成我们从1~50中选一定数目的数使其最总和最接近119.5179003017603885,
应该就是一个动态规划的问题了吧？

KeyTo9_Fans不赞同，认为这是0-1背包问题, 表示没有有效算法。
对于$N=50$，分$2$组，每组$25$，各有$2^{25}=33554432$种结果。 把$2$组结果列成两张表，对其排序。接下来的工作你知道的。就是顺序枚举第$1$张表取哪个数，然后倒序查看第$2$张表，保持结果最接近但不超过$119.5179003017603885$。 不过他的说明不够详细，大家都不是很明白。
medie2005紧接着提出他的想法, 认为可以对数据进行量化:
求出$sqrt(1),sqrt(2),...,sqrt(50)$, 将它们都乘以$10^6$，并向下取整，得到：
$a_{1},a_{2},...,a_{50}$
设一个分组为：
${b_{1},b_{2},...,b_{k}}$
如果${b_{1},b_{2},...,b_{k}}$是最优分组，我们可以知道$b_{1}+b_{2}+...+b_{k}$只能是119517900，119517901，...，119517949中的一个。
从上面的数值中选定一个，比如选119517900，然后，我们得到了：
$b_{1}+b_{2}+...+b_{k}=119517900$
选取一个素数模，比如选m=4999。
计算$a_{1}$,$a_{2}$,...,$a_{50}$, 119517900%m。
于是，我们可以通过动态规划来求出全部候选解。
对求得的候选解，我们再进一步验算就可以得到最优解了。
但是mathe认为量化的精度远远不够。
Fans忍无可忍，给出了更加详细的解释:
没想到要真正领会前面的Fans精神竟然如此困难。
无奈之下，只好用数据来说话。
在$\sqrt{1}$,$\sqrt{2}$,$\sqrt{3}$,...,$\sqrt{25}$共$25$个数中，取其子集，有$2^{25}$种选取方案。
把它们的和从小到大排序，得到第$1$张长度为$2^{25}$的表：
$0$
$\sqrt{1}$
$\sqrt{2}$
$\sqrt{3}$
$\sqrt{4}$
$\sqrt{5}$
$\sqrt{1}+\sqrt{2}$
$\sqrt{6}$
$\sqrt{7}$
$\sqrt{1}+\sqrt{3}$
$\sqrt{8}$
$\sqrt{1}+\sqrt{4}$
$\sqrt{9}$
$\sqrt{2}+\sqrt{3}$
$\sqrt{10}$
……
（中间省略$33554415$个数）
……
$\sqrt{2}+\sqrt{3}+\sqrt{4}+...+\sqrt{25}$
\sqrt{1}+\sqrt{2}+\sqrt{3v+...+\sqrt{25}

在$\sqrt{26}$,$\sqrt{27}$,$\sqrt{28}$,...,$\sqrt{50}$共$25$个数中，取其子集，有$2^{25}$种选取方案。
把它们的和从小到大排序，得到第$2$张长度为$2^{25}$的表：
$0$
$\sqrt{26}$
$\sqrt{27}$
$\sqrt{28}$
$\sqrt{29}$
……
（中间省略$33554425$个数）
……
$\sqrt{27}+\sqrt{28}+\sqrt{29}+...+\sqrt{50}$
$\sqrt{26}+\sqrt{27}+\sqrt{28}+...+\sqrt{50}$
好了。
在两张表中各取$1$个数，让这$2$个数的和最接近$\sqrt{1}+\sqrt{2}+\sqrt{3}+...+\sqrt{50}$的一半即可。
如果你说这个步骤需要$2^{25}\times 2^{25}=2^{50}$次运算，那Fans就无话可说了。
因为Fans认为这两个$2^{25}$是相加的而不是相乘的。
所需运算次数为$2^{25}$+$2^{25}$=$2^{26}$。
所以显然地，把$2^{50}$分成两个$2^{25}$相加是最佳方案。
如果不是$N=50$，而是$N=51$，那就没法均分，只好分成$2^{25}$和$2^{26}$了。

liangbch表示还要考虑二分法查找需要的时间和空间复杂度问题.
Fans举例表示可以通过归并的方法降低复杂度，并给出了很具体的例子。
然后大家讨论可以结合Fans的算法和medie2005的量化方法给个比较有效的算法。
zgg___表示还可以稍微优化一下:
对于Fan所提到的分为两大组，可以优化一下，稍稍减少一些计算量： 因为根号下1-50中包括1-7这样的整数，也包括1-5倍根号2这样的数，所以可以把它们分在一起。 一组是根号下13,14,15,17,19,21,22,23,26,29,30,31,33,34,35,37,38,39,41,42,43,46,47；一共23个数，有2^22种组合，可以都算出来存在一个40M的文件中； 另一组是1-7,1-5倍根号2,1-4倍根号3,1-3倍根号5,1-2倍的根号6,7,10,11，29乘16乘11乘7乘4乘4乘4乘4大约9M多种组合。那就搜索这么多次吧。

结果展示

初步结果

wayne首先通过进化的方法给出了一组结果:
{1, 6, 7, 8, 9, 10, 13, 15, 16, 20, 21, 22, 23, 27, 28, 30, 35, 36, 37, 41, 43, 44, 47, 48, 50}
{2, 3, 4, 5, 11, 12, 14, 17, 18, 19, 24, 25, 26, 29, 31, 32, 33, 34, 38, 39, 40, 42, 45, 46, 49}
两组元素的平方根之和的差值 $2.01\times 10^{-8}$.
他说使用的是1stopt软件，对应的代码很简单，为:

Title "D. Knuth";
Constant n = 50;
Parameter x(1:n)[0,1,0];
Minimum = True;
Function abs(2*(sum(i=1:n)(sqrt(i)*x[i]))-sum(i=1:n)(sqrt(i)));

后来他又将结果进化到:
{1, 3, 4, 5, 9, 10, 11, 12, 14, 15, 17, 18, 22, 24, 27, 29, 31, 32, 35, 39, 40, 41, 44, 46, 47, 50}
{2, 6, 7, 8, 13, 16, 19, 20, 21, 23, 25, 26, 28, 30, 33, 34, 36, 37, 38, 42, 43, 45, 48, 49}
两组的差值 4.777E-9

最优结果出现

然后mathe抛出了他的计算结果:
delta=7.14984e-014:[ 1 4 5 7 8 9 12 13 15 16 20 25 27 30 31 33 37 38 41 43 44 46 47 48 49 ]
delta=7.14984e-014:[ 1 5 7 8 9 12 13 15 20 25 27 30 31 33 36 37 38 41 43 44 46 47 48 49 ]
delta=7.14984e-014:[ 4 5 7 8 9 12 13 15 16 20 27 30 31 33 36 37 38 41 43 44 46 47 48 49 ]
delta=7.14984e-014:[ 5 7 8 12 13 15 16 20 25 27 30 31 33 36 37 38 41 43 44 46 47 48 49 ]
delta=7.14845e-014:[ 1 4 7 8 9 12 13 15 16 25 27 30 31 33 37 38 41 43 44 45 46 47 48 49 ]
delta=7.14845e-014:[ 7 8 12 13 15 16 25 27 30 31 33 36 37 38 41 43 44 45 46 47 48 49 ]
delta=7.14845e-014:[ 4 7 8 9 12 13 15 16 27 30 31 33 36 37 38 41 43 44 45 46 47 48 49 ]
delta=7.14845e-014:[ 1 7 8 9 12 13 15 25 27 30 31 33 36 37 38 41 43 44 45 46 47 48 49 ]
但是离10秒钟的目标还是有很大的差距的。只是他贴出来的代码没能保留住，好像丢失了。
liangbch紧接着给出了他的代码，可以在31秒中找到其中一组结果.

速度优化

KeyTo9_Fan_Fans紧接着给出了她的代码（注意不是Fans而是Fans_Fan）和算法介绍:
嗯，先给出我的答案吧：
方案是
1 4 7 8 9 12 13 15 16 25 27 30 31 33 37 38 41 43 44 45 46 47 48 49
2 3 5 6 10 11 14 17 18 19 20 21 22 23 24 26 28 29 32 34 35 36 39 40 42 50
两组之和的差为1.43e-13。
程序运行时间约11秒。（由于机器是前年的笔记本，在台式机上开一些编译优化什么的应该可以期待跑在10s以内……）
大致算法：
将50个数分为两组，每组25个，分别记为组A和组B。然后分别将组A和组B的所有数字组合（都是2^25种）枚举、排序，存入两个数组list1和list2。然后从上到下枚举list1中的所有元素，从list2中找到一个元素，使得两者的和在不超过sum的一半的情况下最大。因为本题相当于使得小的那部分尽量大，因此这样就可以求出最佳解。
时间复杂度分析：
枚举数字组合中，首先，初始数组中只有一个元素0。然后循环执行如下步骤，将所有的元素添加入数组：（假设当前待添加的元素是x）
将数组复制一份，其中一份不变，另一份每个元素＋x。然后归并排序。
这样复杂度就是O(2^25)的了。
枚举list1时，以一个指针x表示x从list1的第一个元素枚举到最后一个元素；以一个指针y表示对应于当前的x，满足条件的最大的元素的位置。不难发现当x单调递增时y一定是单调递减的。因此复杂度也是O(2^25)。
空间复杂度分析：
归并排序时，以一个数组list1记录当前的数字组合，然后准备一个数组L来表示复制出的另一份数字组合，归并时从后往前在list1中填入数字。这样就可以充分利用list1中的空间，同时保证不会出现冲突的情况。这样，以list1和list2记录两串元素，分别为2^25，然后以L记录复制出的数字串，为2^24。总使用空间约640MB。这样机器会稍微卡一点，但还是可以接受的。
还揭秘了与Fans之间的竞争史，充分显示了ACMers之间互补合作的重要性:
本题是KeyTo9Fans大牛丢给他的手下FansFans的。按照Fans大牛的说法，这是一道水题，咱不屑于切，杀鸡焉用牛刀，看你那么久没来逛论坛了，就交给你了吧！其实Fans大牛也是苦思冥想了半天的，嗯，这里FansFans小朋友就不揭穿他了:D
Fans大牛的形象是光辉的！伟大的！这种题对于他来说不过是小菜一碟！（嘛，反正事实大家都清楚:D Fans大牛典型的想法灰常好代码灰常那个的，反正手下嘛，用来堆代码做苦力的，有FansFans在就不用亲自披挂上阵了，多好:D）
最后插一个小花絮……Fans大牛以为FansFans不打算写，在楼上先开始写了，结果还是被FansFans抢先写完喽～
FansFans现在不知道该说啥，又急着打游戏去，所以说的挺没逻辑的，窘……反正中心思想是：代码是FansFans的，想法是Fans的，嗯。
另外Fans还有一些改进，不过这些就交给Fans说明了，FansFans就不越俎代庖了，嗯。
比较神奇的是Fan\Fans使用的Fans提供的量化表格竟然和mathe的一字不差。

总结

KeyTo9_Fans还对上面代码做了总结性发言：
Fans的想法基本上都实现了。
制作列表，扫描列表都是$O(n)$的。
只可惜没有足够的内存保存各个数值对应的选数方案。
所以不得不先把最优结果算出来，然后调用了$2^{25}$次check过程，逐一检查到底是哪种选数方案得到这样的结果。
而check过程里面还有一层循环。
这使得逐一检查方案的时间复杂度为$O(n\log(n))$。
所幸的是，这部分操作的常数因子比快速排序的常数因子小，所以总的运行时间少了。
要继续改进的话，得把zgg___的精神付诸实现。
只有充分领会了zgg___的精神，才能真正实现$O(n)$制表、$O(n)$扫表、$O(n)$出方案的美好愿望。