问题起源

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}%m,a_{2}%m,…,a_{50}%m, 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{3}+…+\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之间互补合作的重要性:
本题是KeyTo9_Fans大牛丢给他的手下Fans_Fans的。按照Fans大牛的说法,这是一道水题,咱不屑于切,杀鸡焉用牛刀,看你那么久没来逛论坛了,就交给你了吧!其实Fans大牛也是苦思冥想了半天的,嗯,这里Fans_Fans小朋友就不揭穿他了:D
Fans大牛的形象是光辉的!伟大的!这种题对于他来说不过是小菜一碟!(嘛,反正事实大家都清楚:D Fans大牛典型的想法灰常好代码灰常那个的,反正手下嘛,用来堆代码做苦力的,有Fans_Fans在就不用亲自披挂上阵了,多好:D)
最后插一个小花絮……Fans大牛以为Fans_Fans不打算写,在楼上先开始写了,结果还是被Fans_Fans抢先写完喽~
Fans_Fans现在不知道该说啥,又急着打游戏去,所以说的挺没逻辑的,窘……反正中心思想是:代码是Fans_Fans的,想法是Fans的,嗯。
另外Fans还有一些改进,不过这些就交给Fans说明了,Fans_Fans就不越俎代庖了,嗯。
比较神奇的是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)出方案的美好愿望。