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

mathe

求最优解不难，一下四组皆可 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 1, 5, 7, 8, 9, 12, 13, 15, 20, 25, 27, 30, 31, 33, 36, 37, 38, 41, 43, 44, 46, 47, 48, 49 1, 4, 7, 8, 9, 12, 13, 15, 16, 25, 27, 30, 31, 33, 37, 38, 41, 43, 44, 45, 46, 47, 48, 49 7, 8, 12, 13, 15, 16, 25, 27, 30, 31, 33, 36, 37, 38, 41, 43, 44, 45, 46,47, 48, 49 和为 119.5179003017603207542302960921700499402435778084733414943130797735074 所有和的一半为119.5179003017603922470202231131221884062508285908309350855973734662694 误差为$7.15*10^-14$

zgg___

mathe三十一层的解说明他计算力挺强。赫赫。 想不出比Fan三层给的算法更有效的了。 对于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多种组合。那就搜索这么多次吧。

mathe

最优解是8组而不是4组，我前面漏了一半。 程序就是用Fans的方法，因为不不需要考虑10秒的限制。而且说实在，有这时间去做优化，这个慢的版本的程序的结果早就出来了 让程序继续搜索更大范围的解，可以得到更多一点的较优解: delta=6.40363e-013:[ 1 2 3 4 6 7 9 10 12 14 15 16 20 21 23 24 26 29 35 37 38 41 42 43 44 45 47 ] delta=6.40363e-013:[ 2 3 4 6 7 9 10 12 14 15 20 21 23 24 25 26 29 35 37 38 41 42 43 44 45 47 ] delta=6.40363e-013:[ 1 2 3 6 7 10 12 14 15 16 20 21 23 24 25 26 29 35 37 38 41 42 43 44 45 47 ] delta=6.40349e-013:[ 2 4 6 7 9 10 14 15 20 21 23 24 25 26 27 29 35 37 38 41 42 43 44 45 47 ] delta=6.40349e-013:[ 1 2 6 7 10 14 15 16 20 21 23 24 25 26 27 29 35 37 38 41 42 43 44 45 47 ] delta=6.40349e-013:[ 1 2 4 6 7 9 10 14 15 16 20 21 23 24 26 27 29 35 37 38 41 42 43 44 45 47 ] delta=6.40363e-013:[ 2 3 6 7 10 12 14 15 16 20 21 23 24 26 29 35 36 37 38 41 42 43 44 45 47 ] delta=6.40363e-013:[ 1 2 3 6 7 9 10 12 14 15 20 21 23 24 26 29 35 36 37 38 41 42 43 44 45 47 ] delta=6.40349e-013:[ 2 6 7 10 14 15 16 20 21 23 24 26 27 29 35 36 37 38 41 42 43 44 45 47 ] delta=6.40349e-013:[ 1 2 6 7 9 10 14 15 20 21 23 24 26 27 29 35 36 37 38 41 42 43 44 45 47 ] delta=6.40363e-013:[ 2 3 6 7 9 10 12 14 15 20 21 23 24 26 29 35 37 38 41 42 43 44 45 47 49 ] delta=6.40363e-013:[ 1 2 3 4 6 7 10 12 14 15 20 21 23 24 26 29 35 37 38 41 42 43 44 45 47 49 ] delta=6.40349e-013:[ 2 6 7 9 10 14 15 20 21 23 24 26 27 29 35 37 38 41 42 43 44 45 47 49 ] delta=6.40349e-013:[ 1 2 4 6 7 10 14 15 20 21 23 24 26 27 29 35 37 38 41 42 43 44 45 47 49 ]

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 ] delta=2.62609e-013:[ 1 3 8 9 11 14 16 17 18 20 21 24 25 26 28 31 32 33 36 38 39 41 42 47 50 ] delta=2.72074e-013:[ 1 4 6 7 8 9 10 12 15 16 18 19 20 24 25 29 30 32 34 38 39 40 41 45 47 50 ] delta=2.72074e-013:[ 4 6 7 8 9 10 12 15 16 18 19 20 24 29 30 32 34 36 38 39 40 41 45 47 50 ] delta=2.72074e-013:[ 6 7 8 10 12 15 16 18 19 20 24 25 29 30 32 34 36 38 39 40 41 45 47 50 ] delta=2.72074e-013:[ 1 6 7 8 9 10 12 15 18 19 20 24 25 29 30 32 34 36 38 39 40 41 45 47 50 ] delta=2.62609e-013:[ 1 3 4 8 11 14 16 17 18 20 21 24 25 26 28 31 32 33 38 39 41 42 47 49 50 ] delta=2.62609e-013:[ 3 8 9 11 14 16 17 18 20 21 24 25 26 28 31 32 33 38 39 41 42 47 49 50 ] delta=2.62609e-013:[ 1 3 8 11 14 17 18 20 21 24 25 26 28 31 32 33 36 38 39 41 42 47 49 50 ] delta=2.62609e-013:[ 3 4 8 11 14 16 17 18 20 21 24 26 28 31 32 33 36 38 39 41 42 47 49 50 ] delta=2.62609e-013:[ 1 3 4 8 9 11 14 17 18 20 21 24 26 28 31 32 33 36 38 39 41 42 47 49 50 ] delta=2.72074e-013:[ 1 4 6 7 8 10 12 15 18 19 20 24 25 29 30 32 34 38 39 40 41 45 47 49 50 ] delta=2.72074e-013:[ 6 7 8 9 10 12 15 18 19 20 24 25 29 30 32 34 38 39 40 41 45 47 49 50 ] delta=2.72074e-013:[ 1 6 7 8 9 10 12 15 16 18 19 20 24 29 30 32 34 38 39 40 41 45 47 49 50 ] delta=2.72074e-013:[ 4 6 7 8 10 12 15 18 19 20 24 29 30 32 34 36 38 39 40 41 45 47 49 50 ][code] // sumsqr.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include using namespace std; #define N 50 #define M (N/2) unsigned long long data[]={

liangbch

先贴出我的计算结果。 50个数的和是 239.0358006035207600 得到的1个数组是:[7,8,12,13,15,16,25,27,30,31,33,36,37,38,41,43,44,45,46,47,48,49] 这个数组的和是：119.5179003017603200 运行时间：31360 ms 主要的瓶颈是调用VC的快速排序很耗时。如果改用自己写的快速排序，速度可以更快些。

liangbch

再贴出代码，主要算法思想 参考自 10楼。 在我的电脑上，总的运行时间大约31秒，其中快速排序时间18.5秒。

2. #include "stdafx.h"
3. #include "math.h"
4. #include "stdlib.h"
5. #include "search.h"
6. #include "memory.h"
7. #include "string.h"
8. #include "windows.h"
10. typedef unsigned long DWORD;
11. #define MAX_N (50)
13. #define TRUE 1
14. #define FALSE 0
17. typedef struct
18. {
19. DWORD bitMap;
20. DWORD sum;
21. }SQRT_SUM;
24. typedef struct
25. {
26. DWORD bitMap1;
27. DWORD bitMap2;
28. double sum;
29. }SQRT_SUM_RST;
32. double g_sqrt_arr[MAX_N];
33. SQRT_SUM *pTab1=NULL;
34. SQRT_SUM *pTab2=NULL;
36. DWORD mask_arr[]=
37. {
38. 1, 1<<1, 1<<2, 1<<3, 1<<4,
39. 1<<5, 1<<6, 1<<7, 1<<8, 1<<9,
40. 1<<10, 1<<11, 1<<12, 1<<13, 1<<14,
41. 1<<15, 1<<16, 1<<17, 1<<18, 1<<19,
42. 1<<20, 1<<21, 1<<22, 1<<23, 1<<24
43. };
45. double g_half_sum;
48. int __cdecl ItemCmp( const void *element1, const void *element2 )
49. {
50. SQRT_SUM *p1,*p2;
51. p1=(SQRT_SUM *)element1;
52. p2=(SQRT_SUM *)element2;
54. if (p1->sum > p2->sum )
55. return 1;
56. else if (p1->sum <p2->sum )
57. return -1;
58. else
59. return 0;
60. }
63. int InitData()
64. {
65. DWORD i,j;
66. DWORD key,t;
67. double s=0.00;
69. for ( i=0;i<MAX_N;i++)
70. {
71. g_sqrt_arr[i]= sqrt((double)(i+1));
72. s+=g_sqrt_arr[i];
73. }
74. printf("\nsum=%.16f\n",s);
75. g_half_sum =s * 0.5;
77. pTab1=new SQRT_SUM[ 1<<25 ];
78. pTab2=new SQRT_SUM[ 1<<25 ];
80. if ( pTab1==NULL || pTab2==NULL )
81. {
82. printf("No memrory");
83. return FALSE;
84. }
85. //---------------
87. for (key=0; key < (1 << 25); key++)
88. {
90. for (s=0.00,j=0; j<25;j++)
91. {
92. if (key & mask_arr[j] )
93. {
94. s+= g_sqrt_arr[j];
95. }
96. }
97. pTab1[key].bitMap=key;
98. pTab1[key].sum= (DWORD)(s* 8388608.00+0.5);
99. }
101. for (key=0; key < (1 << 25); key++)
102. {
104. s=0;
105. for (j=0; j<25;j++)
106. {
107. if (key & mask_arr[j] )
108. {
109. s+= g_sqrt_arr[j+25];
110. }
111. }
112. pTab2[key].bitMap=key;
113. pTab2[key].sum= (DWORD)(s* 8388608.00+0.5);
114. }
115. //----------------------------------
116. t=GetTickCount();
117. qsort( (void *)pTab1, (size_t)(1<<25), sizeof( SQRT_SUM), ItemCmp );
118. qsort( (void *)pTab2, (size_t)(1<<25), sizeof( SQRT_SUM), ItemCmp );
119. t=GetTickCount()-t;
121. printf("It take %d ms for sort 2 arrays\n",t);
123. return TRUE;
124. }
126. void unInitData()
127. {
128. if ( pTab1 !=NULL)
129. {
130. delete[] pTab1; pTab1=NULL;
131. }
133. if ( pTab2 !=NULL)
134. {
135. delete[] pTab2; pTab2=NULL;
136. }
137. }
139. int binSearch( const SQRT_SUM* pTab, DWORD n, int end, int *pLow, int *pHigh)
140. {
141. int low,high,mid;
142. //-----------------
143. low=0;
144. high=end;
145. while (1)
146. {
147. if (high-low<=1)
148. {
149. break;
150. }
151. else
152. {
153. mid=(low+high)/2;
154. if (n>=pTab[mid].sum)
155. low=mid;
156. else
157. high=mid-1;
158. }
159. }
161. if ( pTab[low].sum >= n-1)
162. low--;
163. low++;
164. if ( pTab[high].sum <= n+1)
165. high++;
166. high--;
167. *pLow=low;
168. *pHigh=high;
169. return (low<=high);
170. }
172. double getDouble( int tabNo, DWORD key)
173. {
174. double r;
175. int i;
177. for (r=0.00,i=0;i<25;i++)
178. {
179. if (key & mask_arr[i] )
180. {
181. if (tabNo==0)
182. r+= g_sqrt_arr[i];
183. else
184. r+= g_sqrt_arr[i+25];
185. }
186. }
187. return r;
188. }
190. double printfArray(DWORD key1,DWORD key2)
191. {
192. int i;
193. double s=0;
195. printf("[");
196. for (i=0;i<25;i++)
197. {
198. if (key1 & mask_arr[i] )
199. {
200. printf("%d,",i+1);
201. s+= sqrt( (double)(i+1));
202. }
204. }
205. for (i=0;i<25;i++)
206. {
207. if (key2 & mask_arr[i] )
208. {
209. printf("%d,",i+26);
210. s+= sqrt( (double)(i+26));
211. }
213. }
214. printf("]");
215. return s;
216. }
218. void search(int lmt,int *pIdx1,int *pIdx2)
219. {
220. int i,j,end;
221. double minDiff=1000000;
222. int idx1,idx2;
224. end=(1<<25)-1;
225. for (i=0;i< (1<<25) ; i++)
226. {
227. double f1,f2;
228. DWORD n1;
229. int high,low;
231. n1= pTab1[i].sum;
232. if ( binSearch(pTab2,lmt-n1,end,&low,&high) )
233. {
234. f1=getDouble( 0, pTab1[i].bitMap);
236. for (j=low;j<=high;j++)
237. {
238. f2=getDouble( 1, pTab2[j].bitMap);
239. if ( fabs( f1+ f2 - g_half_sum)<minDiff)
240. {
241. minDiff=fabs( f1+ f2 - g_half_sum);
242. idx1=i;
243. idx2=j;
244. }
246. }
247. if (high<end)
248. end=high;
249. }
250. }
251. *pIdx1=idx1;
252. *pIdx2=idx2;
253. }
255. int main(int argc, char* argv[])
256. {
257. double s;
258. DWORD t1,t2,lmt;
259. int idx1,idx2;
261. t1=GetTickCount();
262. InitData();
263. lmt= (DWORD)(g_half_sum * 8388608.00+0.5);
265. search(lmt,&idx1,&idx2);
266. printf("\narray1 is:\n");
267. s=printfArray(pTab1[idx1].bitMap,pTab2[idx2].bitMap);
268. printf("\nThe sum is %.16f\n",s);
270. unInitData();
271. t2=GetTickCount()-t1;
272. printf("\nIt take %u ms\n",t2);
274. return 0;
275. }
277. }

复制代码

KeyTo9_Fan_Fans

嗯，先给出我的答案吧： 方案是 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。这样机器会稍微卡一点，但还是可以接受的。 程序清单：（我的代码风格不太好，窘……）

1. #include <stdio.h>
2. #include <iostream>
4. using namespace std;
6. const int MaxN = 1 << 25;
8. int n, i, j, k, x, y;
9. int out[60]; // 记录输出方案，其中out[x]==1表示方案中元素x属于少的那部分
10. unsigned long long sum, ans, ans_x, ans_y; // ans记录少的那半的总和，ans_x记录右半边元素的和，ans_y记录左半边元素的和
11. unsigned long long a[60]; // 记录输入的50个元素
12. unsigned long long list1[MaxN], list2[MaxN], L[MaxN >> 1]; // 含义如上所述
14. void make(int st, int ed) // 构造2^25的有序数列
15. {
16. int i, j, k, x, y;
18. list1[0] = 0;
19. for (i=st; i<ed; i++)
20. {
21. for (j=0; j<(1<<(i-st)); j++) L[j] = list1[j] + a[i];
22. x = y = (1 << (i - st)) - 1;
23. for (k=(1<<(i-st+1))-1; k>=0; k--)
24. {
25. if (x>=0 && (y<0 || list1[x]>L[y])) { list1[k] = list1[x]; x --; }
26. else { list1[k] = L[y]; y --; }
27. }
28. }
29. }
31. bool check(int st, int ed, unsigned long long S, int mask) // 检查相应的方案mask是否可以得到和S
32. {
33. int i;
35. for (i=st; i<ed; i++) if (mask & (1 << (i - st))) S -= a[i];
36. if (!S)
37. {
38. for (i=st; i<ed; i++) if (mask & (1 << (i - st))) out[i] = 1;
39. return 1;
40. } else return 0;
41. }
43. int main()
44. {
45. freopen("1.in", "r", stdin);
46. scanf("%d", &n);
47. for (i=0; i<n; i++) // 输入
48. {
49. cin >> a[i];
50. sum += a[i];
51. }
53. make(0, n / 2); // 构造前半
54. for (i=0; i<(1<<(n/2)); i++) list2[i] = list1[i]; // 存入list2中
55. make(n / 2, n); // 构造后半，此时前半在list2，后半在list1
56. y = (1 << (n / 2)) - 1; // list2中的指针
57. for (x=0; x<(1<<(n/2)); x++) // list1中的指针
58. {
59. while (y && list1[x]+list2[y]>sum/2) y --; // 找到最大的满足条件的y
60. if (list1[x]+list2[y]>ans && list1[x]+list2[y]<=sum/2) // 若满足条件且大于当前解则更新
61. {
62. ans = list1[x] + list2[y];
63. ans_x = list1[x];
64. ans_y = list2[y];
65. }
66. }
67. freopen("1.out", "w", stdout); // 输出
68. for (i=0; i<(1<<(n/2)); i++) if (check(0, n / 2, ans_y, i)) break;
69. for (i=0; i<(1<<(n/2)); i++) if (check(n / 2, n, ans_x, i)) break;
70. for (i=0; i<n; i++) if (out[i]) printf("%d ", i + 1); printf("\n");
71. for (i=0; i<n; i++) if (!out[i]) printf("%d ", i + 1); printf("\n");
72. cout << ans << " " << sum - ans - ans << endl;
73. }

复制代码

输入数据：（这些数据是相应的实数乘以2^56取整的结果，Fans友情提供） 50 72057594037927936 101904826760412361 124807413944863399 144115188075855872 161125678563890424 176504337485538768 190646473898007863 203809653520824722 216172782113783808 227866119871621714 238988002719557251 249614827889726798 259807350090317420 269614829005170980 279077861676669750 288230376151711744 297101071346254269 305714480281237083 314091770526006817 322251357127780848 330209379075203405 337980074690455987 345576080981165471 353008674971077535 360287970189639680 367423078101941656 374422241834590198 381292947796015726 388042019499834581 394675696941228988 401199704155648221 407619307041649444 413939363109682179 420164364493449324 426298475306584890 432345564227567616 438309233037348441 444192841707656799 449999530536264313 455732239743243429 461393726875353099 466986582310951157 472513243112822805 477976005439114502 483377035691671273 488718380555307200 494001976059951504 499229655779453597 504403158265495552 509524133802061805 输出数据： 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 8612172340209789951 10302 个人感想： 本题是KeyTo9_Fans大牛丢给他的手下Fans_Fans的。按照Fans大牛的说法，这是一道水题，咱不屑于切，杀鸡焉用牛刀，看你那么久没来逛论坛了，就交给你了吧！其实Fans大牛也是苦思冥想了半天的，嗯，这里Fans_Fans小朋友就不揭穿他了 Fans大牛的形象是光辉的！伟大的！这种题对于他来说不过是小菜一碟！（嘛，反正事实大家都清楚 Fans大牛典型的想法灰常好代码灰常那个的，反正手下嘛，用来堆代码做苦力的，有Fans_Fans在就不用亲自披挂上阵了，多好） 最后插一个小花絮……Fans大牛以为Fans_Fans不打算写，在楼上先开始写了，结果还是被Fans_Fans抢先写完喽～ Fans_Fans现在不知道该说啥，又急着打游戏去，所以说的挺没逻辑的，窘……反正中心思想是：代码是Fans_Fans的，想法是Fans的，嗯。 另外Fans还有一些改进，不过这些就交给Fans说明了，Fans_Fans就不越俎代庖了，嗯。 （话说不知道Fans是啥想法，看到Fans_Fans在这里这么说居然兴奋的红光满面OTL）

mathe

表格显然是抄我的 这个题目的确有点水，不过要限定时间还是有点繁琐的.

mathe

36#的make函数还是比较巧妙的。我直接构造所有数据然后sort都不只10秒

KeyTo9_Fans

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

mathe

上面过程还有唯一的问题是没有进行误差分析（不过这个属于鸡蛋里面挑骨头了）。 还有36#充分体现了ACMer们分工合作，各司其职的重要性（如同男耕女织一样）