高德纳书中一道很普通的题目

sw2wolf

将 sqrt 1，sqrt 2， ... , sqrt 50 ( 1 到 50的平方根）分成两组，把每组中的数相加，得出两个数， 然后比较这两个数的差别。 问题： 用常见的计算机语言之一编写一个程序，找出最小的差别的两组， 要求该程序在计算机上运算得出结果所花费的时间不超过10秒。

------->

1. import Data.List
3. samp = [sqrt x | x <- [1..50]]
5. minDiff = (sort [(abs \$ (sum x) - (sum \$ samp\\x), x) | x <- subsequences samp]) !! 0

复制代码

这是最笨的方法（穷举）， 如果你要试请先将50改成10， 否则后果自负

最佳答案，及程序源码 请见： 33# mathe

---gxqcn

winxos

可以这样来考虑吧， $\sqrt{1}+\sqrt{2}+...+\sqrt{50}=239.0358006035207771$ 一半等于 $119.5179003017603885$ 问题变成我们从1~50中选一定数目的数使其最总和最接近119.5179003017603885 应该就是一个动态规划的问题了吧？

KeyTo9_Fans

非也。 $01$背包问题。 没有有效算法。 对于$N=50$，分$2$组，每组$25$，各有$2^25=33554432$种结果。 把$2$组结果列成两张表，对其排序。 接下来的工作你知道的。 就是顺序枚举第$1$张表取哪个数，然后倒序查看第$2$张表，保持结果最接近但不超过$119.5179003017603885$。

winxos

3# KeyTo9_Fans 学习了， 不过题目中说分两组并没有说数目一样，所以情况还是要很大的吧。。。

medie2005

没说两组个数相等啊。 应该有些数学关系吧。

hujunhua

$\sum_(n=1)^31 \sqrt{n}=117.651$ 所以分组最偏也就是31项对19项了

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

50个数中部分和有$2^50$中情况，所以平均来看应该存在一组数，同正好一半的误差小于$239/{2^50}$ 所以上面的方法还远远不够

liangbch

将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$

KeyTo9_Fans

没想到要真正领会$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$了。