最少分组方案算法

无心人

不是吧 只要正向得到 形式如2pq + 1 类型素数就可以了吧

sunwukong

对 2048 以内的素数分组 有 92 组的结果： No. 1 : 2039 2029 1033 No. 2 : 2027 2017 1049 No. 3 : 2011 2003 1063 No. 4 : 1999 1997 1069 No. 5 : 1993 1987 1061 No. 6 : 1979 1973 1097 No. 7 : 1951 1949 1129 No. 8 : 1933 1931 1123 No. 9 : 1913 1907 1171 No. 10 : 1901 1889 1193 No. 11 : 1879 1877 1217 No. 12 : 1873 1871 1223 No. 13 : 1867 1861 1231 No. 14 : 1847 1831 1259 No. 15 : 1823 1811 1297 No. 16 : 1801 1789 1327 No. 17 : 1787 1783 1321 No. 18 : 1777 1759 1373 No. 19 : 1753 1747 1399 No. 20 : 1741 1733 1423 No. 21 : 1723 1721 1447 No. 22 : 1709 1699 1471 No. 23 : 1697 1693 1493 No. 24 : 1669 1667 1543 No. 25 : 1663 1657 1553 No. 26 : 1637 1627 1609 No. 27 : 1621 1619 1613 No. 28 : 1607 1601 1597 No. 29 : 1583 1579 1571 No. 30 : 1567 1559 1549 No. 31 : 1531 1523 1511 No. 32 : 1499 1489 1487 No. 33 : 1483 1481 1459 No. 34 : 1453 1451 1439 No. 35 : 1433 1429 1427 No. 36 : 1409 1381 1367 No. 37 : 1361 1319 1307 No. 38 : 1303 1301 1291 No. 39 : 1289 1283 1279 2 No. 40 : 1277 1249 1237 No. 41 : 1229 1213 1201 No. 42 : 1187 1181 1163 No. 43 : 1153 1151 1117 No. 44 : 1109 1103 1093 3 No. 45 : 1091 1087 1051 No. 46 : 1039 1031 1021 No. 47 : 1019 1013 1009 No. 48 : 997 991 983 No. 49 : 977 971 967 No. 50 : 953 947 941 5 No. 51 : 937 929 919 No. 52 : 911 907 887 No. 53 : 883 881 877 No. 54 : 863 859 857 No. 55 : 853 839 829 7 No. 56 : 827 823 821 No. 57 : 811 809 797 No. 58 : 787 773 769 No. 59 : 761 757 751 No. 60 : 743 739 733 No. 61 : 727 719 709 11 No. 62 : 701 691 683 No. 63 : 677 673 661 13 No. 64 : 659 653 647 No. 65 : 643 641 631 No. 66 : 619 617 613 17 No. 67 : 607 601 599 19 No. 68 : 593 587 577 No. 69 : 571 569 563 23 No. 70 : 557 547 541 No. 71 : 523 521 509 29 No. 72 : 503 499 491 31 No. 73 : 487 479 467 37 No. 74 : 463 461 457 43 No. 75 : 449 443 439 47 No. 76 : 433 431 421 53 No. 77 : 419 409 401 61 No. 78 : 397 389 383 71 No. 79 : 379 373 367 79 No. 80 : 359 353 349 97 No. 81 : 347 337 331 109 No. 82 : 317 313 311 139 No. 83 : 307 293 283 167 No. 84 : 281 277 271 199 No. 85 : 269 263 257 233 No. 86 : 251 241 239 229 No. 87 : 227 223 211 197 No. 88 : 193 191 181 179 No. 89 : 173 163 157 151 No. 90 : 149 137 131 127 No. 91 : 113 107 103 83 41 No. 92 : 101 89 73 67 59

gxqcn

楼上说说，你是如何做到的？ 这个悬赏至今刚好满一个月了， 之前一直没有更好的突破， 所以，打算继续悬赏一个月， 对于有突破的算法或结论， 除了可以得到悬赏的100枚金币， 还可获得本人私下转让的金币（数目不菲的）。

sunwukong

1. #include < iostream.h >
2. #include < math.h >
4. #include "D:/HugeCalc/HugeCalc.h" // 公共接口
5. #include "D:/HugeCalc/HugeInt.h" // 10进制系统
6. #include "D:/HugeCalc/HugeIntX.h" // 16进制系统
8. #pragma message( "automatic link to D:/HugeCalc/HugeCalc.lib" )
9. #pragma comment( lib, "D:/HugeCalc/HugeCalc.lib" )
11. const unsigned __int16 Pri1024 = 172; // 1024 以内的素数个数
12. const unsigned __int16 Pri2048 = 309; // 2048 以内的素数个数
14. const __int64 BOUND32 = (1ul << 32) - 1;
15. const __int64 BOUND14 = (1ul << 14) - 1;
16. const __int64 BOUND10 = (1ul << 10) - 1;
18. typedef CHugeIntX integer;
20. unsigned __int16 arr[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039 };
22. //const unsigned __int32 ProblemSize = 1023;
23. //unsigned __int16 arr[ProblemSize];
25. __int32 MinimumGroup(const unsigned __int16* const arr, const unsigned __int16 _SIZE, const __int64 _BOUND);
27. int main(/*int argc, char* argv[]*/ void)
28. {
29. __int32 result;
31. //for ( __int16 i=0; i<ProblemSize; i++) arr[ i ] = i + 2;
32. cout << "Call " << HugeCalc::GetVer() << endl;
34. HugeCalc::EnableTimer();
35. HugeCalc::ResetTimer(0, TIMER_UNIT_ms);
37. //result = MinimumGroup(arr, ProblemSize, BOUND32);
38. //result = MinimumGroup(arr, 25, BOUND14); // 贪婪法=10，最优=9
39. //result = MinimumGroup(arr, 36, 22500ul); // 贪婪法=15，最优=14
40. //result = MinimumGroup(arr, 72, 8100ul); // 贪婪法=最优=49
41. //result = MinimumGroup(arr, Pri1024, BOUND10); // 贪婪法=最优=162
42. //result = MinimumGroup(arr, Pri1024, BOUND10*29); // 贪婪法=最优=133
43. result = MinimumGroup(arr, Pri1024, BOUND32);
44. //result = MinimumGroup(arr, Pri2048, BOUND32);
46. HugeCalc::EnableTimer( FALSE );
48. cout << endl << "Best result = " << result << endl;
50. cout << endl << HugeCalc::GetTimerStr() << endl;
52. system( "pause" );
54. return 0;
55. }
57. // 函数名： MinimumGroup
58. // 函数功能： 求出把一组正整数 arr[0] ~ arr[_SIZE-1] 划分成最少的组数的方法，使得每组里所有数之积均不大于 _BOUND
59. //
60. // 输入参数:
61. // arr： unsigned __int16，数组指针，要求 arr[] 是升序排列
62. // _SIZE： unsigned __int16，数组的大小
63. // _BOUND： __int64，分组的乘积最大值
64. //
65. // 输出参数： __int32，最小分组数
66. // 结果为 0： _SIZE = 0
67. // 结果为 -1： _BOUND < arr[_SIZE-1]
68. // 结果为 -2： arr 不是升序排列
69. //
70. // 版本 ： 1.2.5.9
71. // 修改时间： 2008-9-11 00:30
72. //
73. // 存在问题： 运算效率很低，限界条件不够精细
74. // 下一版本改进措施； 乘法变加法，把 arr[]、_BOUND 都取对数，然后扩大某个倍数，化成整数加减运算
76. __int32 MinimumGroup(const unsigned __int16* const arr, const unsigned __int16 _SIZE, const __int64 _BOUND)
77. {
78. __int32 i, j, k, icur, g, gMin, gMax, gCur, top, bottom, top0, bottom1, top1, Lpro, numOfBig, Lpromin;
79. __int32 *bUsed, *pbuf;
81. __int64 product, maxV, minGV, *pmaxV, *pminGV, *ppro;
83. top0 = _SIZE - 1;
85. if ( 0 == _SIZE ) return (0);
86. if ( _BOUND < arr[top0] ) return (-1);
88. for ( i=0; i<top0; ++i )
89. {
90. if ( arr[i] > arr[i+1] )
91. return (-2);
92. }
94. if ( 0 == arr[0] || 1 == arr[top0] ) return (1);
96. for ( i=0 ; 1 == arr[i] ; ++i ); // 1不参加运算
98. if ( i == top0 ) return (1);
100. bottom1 = i;
102. for (maxV=_BOUND/arr[bottom1], i=top0 ; i>bottom1 && arr[i]>maxV ; --i ); // 只能单独做一组的数
104. if ( i - bottom1 < 2 ) return (_SIZE - i);
106. top1 = i;
108. integer hollpro(arr[bottom1]), grpV(_BOUND), b(_BOUND);
110. for ( j=1, i=1+bottom1 ; i<=top1 ; ++i )
111. {
112. hollpro *= arr[i];
113. if ( hollpro > grpV )
114. {
115. grpV *= b;
116. ++j;
117. }
118. }
119. grpV = 0;
121. numOfBig = top0 - top1;
122. gMin = j + numOfBig;
123. if ( j == 1 ) return (gMin);
125. // 用贪婪法求分组数的一个上界 gMax，此方法来自 gxqcn
126. bUsed = new __int32 [_SIZE];
128. for ( i=0; i<_SIZE; ++i ) bUsed[i] = 0;
130. cout << endl;
132. for ( gMax=0, bottom=0, top=top0 ; bottom != top ; )
133. {
134. ++gMax;
135. cout << "No. " << gMax << " : ";
137. //for ( product=1, maxV=_BOUND, i=top ; i >= bottom; --i )
138. for ( maxV=_BOUND, i=top ; i >= bottom; --i )
139. {
140. if ( !bUsed[i] && arr[i] <= maxV )
141. {
142. cout << " " << arr[i];
143. //maxV = _BOUND / ( product *= arr[i] );
144. maxV /= arr[i];
145. bUsed[i] = 1;
146. }
147. }
148. //cout << " " << product;
149. cout << endl;
151. while ( bottom != top && bUsed[top] ) --top;
152. while ( bottom != top && bUsed[bottom] ) ++bottom;
153. }
154. if ( !bUsed[top] )
155. {
156. ++gMax;
157. //cout << "No. " << gMax << " : " << arr[top] << " " << arr[top] << endl;
158. cout << "No. " << gMax << " : " << arr[top] << endl;
159. }
161. if ( gMax == gMin )
162. {
163. delete [] bUsed;
164. return (gMax); // 上界 = 下界
165. }
167. // 尝试组数更小的方案
169. // 求第一组的数字的个数
170. for ( Lpromin=0, maxV=_BOUND, i=top1 ; i >= bottom1; --i )
171. {
172. if ( arr[i] <= maxV )
173. {
174. maxV /= arr[i];
175. ++Lpromin;
176. }
177. }
179. k = gMax - numOfBig;
181. for ( maxV=_BOUND, i=bottom1; arr[i]<=maxV; ++i ) maxV /= arr[i] ;
183. Lpro = i - bottom1 + 1; // 最长乘式的因子数+1
184. j = Lpro * gMax;
185. pbuf = new __int32 [j]; // 所有分组因子下标表格
186. pmaxV = new __int64 [j]; // 同组的下一个乘积因子允许的最大值
187. ppro = new __int64 [j]; // 本组前几个因子的乘积
188. pminGV = new __int64 [gMax]; // 每一组乘积允许的最小值
190. integer *pGV, *pB, q, r, c;
192. pGV = new integer [gMax]; // 本组之后未分配的数的乘积
193. pB = new integer [k]; // 界限参数（_BOUND的乘幂）
195. for ( i=0; i<j; ++i ) pbuf[i] = 0;
196. for ( i=0; i<j; ++i ) pmaxV[i] = 0;
197. for ( i=0; i<j; ++i ) ppro[i] = 0;
199. for ( top=top0, i=1; i<=numOfBig ; ++i, --top )
200. {
201. pbuf[i * Lpro ] = 1;
202. pbuf[i * Lpro + 1] = top;
204. ppro[i * Lpro ] = 1;
205. ppro[i * Lpro + 1] = arr[top];
207. bUsed[top] = 1;
208. }
210. icur = Lpro-2+bottom1;
211. if ( Lpromin <= 2 )
212. {
213. for ( i=icur; i<top1; ++i ) pmaxV[i] = _BOUND - ( _BOUND % arr[i] );
214. }
215. else
216. {
217. for ( i=icur; i<top1; ++i )
218. {
219. maxV = _BOUND / arr[i];
220. g = __int32(maxV % arr[bottom1]);
221. for ( j=bottom1+1; g>0 && j<i; ++j)
222. {
223. gCur = __int32(maxV % arr[j]);
224. if ( g > gCur )
225. g = gCur;
226. }
227. pmaxV[i] = ( maxV - g ) * arr[i];
228. }
229. }
231. // 选择排序
232. for ( i=icur; i<icur+k-1; ++i )
233. {
234. for ( g=i, maxV=pmaxV[i], j=i+1; j<top1; ++j )
235. {
236. if ( maxV < pmaxV[j] )
237. {
238. maxV = pmaxV[j];
239. g = j;
240. }
241. }
242. if ( g != i )
243. {
244. pmaxV[g] = pmaxV[i];
245. pmaxV[i]= maxV;
246. }
247. }
249. for ( pB[0]=1, pB[1]=pmaxV[icur], j=icur, i=2; i<k; ++i )
250. {
251. ++j;
252. pB[i] = pB[i-1] * ( q = pmaxV[j] );
253. }
254. //for ( pB[0]=1, pB[1]=b, i=2; i<k; ++i ) pB[i] = pB[i-1] * b;
255. b = 0;
257. for ( i=numOfBig+1; i<gMax; ++i ) pmaxV[i * Lpro] = _BOUND;
259. pGV[numOfBig] = hollpro;
261. for ( gCur=gMax-1 ; gCur >= gMin ; --gCur ) // 组数循环
262. {
263. for ( top=top1, i=bottom=bottom1; i<=top; ++i ) bUsed[i] = 0;
265. for ( g=numOfBig+1 ; g<gCur ; ) // g 循环
266. {
267. q.Div( pGV[g-1], pB[gCur-g], &r );
268. if ( !(!r) ) ++q;
269. pminGV[g] = minGV = q;
271. k = 1;
272. pbuf[g*Lpro+k] = top;
273. ppro[g*Lpro+k] = product = arr[top];
274. pmaxV[g*Lpro+k] = maxV = _BOUND / product;
275. bUsed[top] = 1;
276. icur = --top;
278. // 生成第 g 组乘积
279. do {
280. for ( i=icur; i>=bottom; --i )
281. {
282. if ( !bUsed[i] && arr[i] <= maxV )
283. {
284. ++k;
285. pbuf[g*Lpro+k] = i;
286. ppro[g*Lpro+k] = product *= arr[i];
287. pmaxV[g*Lpro+k] = maxV /= arr[i] ;
288. bUsed[i] = 1;
289. }
290. }
292. if ( product >= minGV ) // 进入下一组
293. {
294. pbuf[g*Lpro] = k;
295. pGV[g] = pGV[g-1] / (c = product);
297. while ( bottom != top && bUsed[top] ) --top;
298. while ( bottom != top && bUsed[bottom] ) ++bottom;
300. ++g;
301. break;
302. }
304. // 生成下一个乘积
305. do {
306. j = bottom;
308. do {
309. i = pbuf[g*Lpro+k];
310. bUsed[i] = 0;
311. --k;
313. if ( i > top )
314. {
315. top = i;
316. }
317. else if ( i < bottom )
318. {
319. bottom = i;
320. }
321. } while ( k >= 1 && i < j );
323. if ( k >= 1 )
324. {
325. icur = --i;
326. maxV = pmaxV[g*Lpro+k];
327. product = ppro[g*Lpro+k];
328. break;
329. }
331. --g; // 退回到上一组
333. if ( numOfBig == g ) // 退到底了
334. {
335. delete [] pB;
336. delete [] pGV;
337. delete [] pminGV;
338. delete [] ppro;
339. delete [] pmaxV;
340. delete [] pbuf;
341. delete [] bUsed;
343. return (gCur+1);
344. }
346. k = pbuf[g*Lpro];
347. minGV = pminGV[g];
349. } while ( 1 ); // end of 生成下一个乘积
351. } while ( 1 ); // end of 生成第 g 组乘积
353. } // end of g 循环
355. for ( j=0, i=top; i>=bottom; --i) // 最后一组
356. {
357. if ( !bUsed[i] )
358. {
359. ++j;
360. pbuf[g*Lpro+j] = i;
361. }
362. }
363. pbuf[g*Lpro] = j;
365. // 输出
366. cout << endl << "groups = " << gCur << endl;
367. for ( i=1 ; i <= gCur ; ++i )
368. {
369. cout << "No. " << i << " : ";
371. for ( k=pbuf[i*Lpro], j=1 ; j <= k ; ++j )
372. cout << " " << arr[ pbuf[i * Lpro + j] ];
374. cout << endl;
375. }
376. cout << endl;
378. } // end of 组数循环
380. delete [] pB;
381. delete [] pGV;
382. delete [] pminGV;
383. delete [] ppro;
384. delete [] pmaxV;
385. delete [] pbuf;
386. delete [] bUsed;
388. return (gMin);
389. }

复制代码

gxqcn

这么说来，我给出的程序效率是很高的，结果也是相当不错的。 谢谢你的代码，有空时我琢磨一下。 前面第26#说了，该问题更注重输出结果，因为是拿它作应用的； 即便运行时间长点也不碍事，反正只要运行一次。 当然，若有更优化的通用算法，则是上上品了。

无心人

为什么不用对数？ 仅仅是因为是浮点运算？ 假设某组数字的对数和为s s <= 32 32 - s <= 1/16 是否算和优化的一组？

aimisiyou

这跟一维下料是等价问题。只求满足根数最少的组合方式之一?(可能有多种)