高德纳书中一道很普通的题目
将 sqrt 1，sqrt 2， ... , sqrt 50 ( 1 到 50的平方根）分成两组，把每组中的数相加，得出两个数， 然后比较这两个数的差别。问题： 用常见的计算机语言之一编写一个程序，找出最小的差别的两组， 要求该程序在计算机上运算得出结果所花费的时间不超过10秒。题虽普通，探讨却很深入。
------->import Data.List
samp = ]
minDiff = (sort [(abs \$ (sum x) - (sum \$ samp\\x), x) | x <- subsequences samp]) !! 0
这是最笨的方法（穷举）， 如果你要试请先将50改成10， 否则后果自负 :)
最佳答案，及程序源码 请见： 33# mathe
---gxqcn 可以这样来考虑吧，
$\sqrt{1}+\sqrt{2}+...+\sqrt{50}=239.0358006035207771$
一半等于 $119.5179003017603885$
问题变成我们从1~50中选一定数目的数使其最总和最接近119.5179003017603885
应该就是一个动态规划的问题了吧？ 非也。
$01$背包问题。
没有有效算法。
对于$N=50$，分$2$组，每组$25$，各有$2^25=33554432$种结果。
把$2$组结果列成两张表，对其排序。
接下来的工作你知道的。
就是顺序枚举第$1$张表取哪个数，然后倒序查看第$2$张表，保持结果最接近但不超过$119.5179003017603885$。 3# KeyTo9_Fans
学习了，
不过题目中说分两组并没有说数目一样，所以情况还是要很大的吧。。。 没说两组个数相等啊。
应该有些数学关系吧。 $\sum_(n=1)^31 \sqrt{n}=117.651$
所以分组最偏也就是31项对19项了 一个想法：
求出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。
于是，我们可以通过动态规划来求出全部候选解。
对求得的候选解，我们再进一步验算就可以得到最优解了。 50个数中部分和有$2^50$中情况，所以平均来看应该存在一组数，同正好一半的误差小于$239/{2^50}$
所以上面的方法还远远不够 将50个数分为2组，考虑其中的一组数，最少有19个数，最多有25个数。
则总的可能组合为Combo(50,19)+Combo(50,20)+Combo(50,21)+Combo(50,22)+Combo(50,23)+Combo(50,24)+Combo(50,25)=5.89615E+14,和$2^50$=1.1259E+15,差别不大。求最优解依然没有突破复杂度$2^50$ 没想到要真正领会$3$楼中的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$*$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$了。