最少分组方案算法

无心人

不是吧
只要正向得到
形式如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 >
   
3. 
   
4. #include "D:/HugeCalc/HugeCalc.h"  // 公共接口
   
5. #include "D:/HugeCalc/HugeInt.h"   // 10进制系统
   
6. #include "D:/HugeCalc/HugeIntX.h"  // 16进制系统
   
7. 
   
8. #pragma message( "automatic link to D:/HugeCalc/HugeCalc.lib" )
   
9. #pragma comment( lib, "D:/HugeCalc/HugeCalc.lib" )
   
10. 
    
11. const unsigned __int16 Pri1024 = 172; // 1024 以内的素数个数
    
12. const unsigned __int16 Pri2048 = 309; // 2048 以内的素数个数
    
13. 
    
14. const __int64 BOUND32 = (1ul << 32) - 1;
    
15. const __int64 BOUND14 = (1ul << 14) - 1;
    
16. const __int64 BOUND10 = (1ul << 10) - 1;
    
17. 
    
18. typedef CHugeIntX integer;
    
19. 
    
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 };
    
21. 
    
22. //const unsigned __int32 ProblemSize = 1023;
    
23. //unsigned __int16 arr[ProblemSize];
    
24. 
    
25. __int32 MinimumGroup(const unsigned __int16* const arr, const unsigned __int16 _SIZE, const __int64 _BOUND);
    
26. 
    
27. int main(/*int argc, char* argv[]*/ void)
    
28. {
    
29.         __int32 result;
    
30.        
    
31.         //for ( __int16 i=0; i<ProblemSize; i++) arr[ i ] = i + 2;
    
32.         cout << "Call " << HugeCalc::GetVer() << endl;
    
33.        
    
34.     HugeCalc::EnableTimer();
    
35.     HugeCalc::ResetTimer(0, TIMER_UNIT_ms);
    
36.        
    
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);
    
45. 
    
46.         HugeCalc::EnableTimer( FALSE );
    
47.        
    
48.         cout << endl << "Best result = " << result << endl;
    
49.        
    
50.         cout << endl << HugeCalc::GetTimerStr() << endl;
    
51.        
    
52.         system( "pause" );
    
53.        
    
54.     return 0;
    
55. }
    
56. 
    
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 都取对数，然后扩大某个倍数，化成整数加减运算
    
75. 
    
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;
    
80.        
    
81.     __int64 product, maxV, minGV, *pmaxV, *pminGV, *ppro;
    
82.        
    
83.         top0 = _SIZE - 1;
    
84.        
    
85.         if ( 0 == _SIZE ) return (0);
    
86.         if ( _BOUND < arr[top0] ) return (-1);
    
87.        
    
88.         for ( i=0; i<top0; ++i )
    
89.         {
    
90.                 if ( arr[i] > arr[i+1] )
    
91.                         return (-2);
    
92.         }
    
93.        
    
94.         if ( 0 == arr[0] || 1 == arr[top0] ) return (1);       
    
95.        
    
96.         for ( i=0 ;  1 == arr[i] ;  ++i ); // 1不参加运算
    
97.        
    
98.         if ( i == top0 ) return (1);
    
99.        
    
100.         bottom1 = i;
     
101.        
     
102.         for (maxV=_BOUND/arr[bottom1], i=top0 ; i>bottom1 && arr[i]>maxV ; --i ); // 只能单独做一组的数
     
103.        
     
104.         if ( i - bottom1 < 2 ) return (_SIZE - i);
     
105.        
     
106.         top1 = i;
     
107.        
     
108.         integer hollpro(arr[bottom1]), grpV(_BOUND), b(_BOUND);
     
109.        
     
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;
     
120.        
     
121.         numOfBig = top0 - top1;
     
122.         gMin = j + numOfBig;
     
123.         if ( j == 1 ) return (gMin);
     
124.        
     
125.         // 用贪婪法求分组数的一个上界 gMax，此方法来自 gxqcn
     
126.         bUsed = new __int32 [_SIZE];
     
127.        
     
128.         for ( i=0; i<_SIZE; ++i ) bUsed[i] = 0;
     
129.        
     
130.         cout << endl;
     
131.        
     
132.     for ( gMax=0, bottom=0, top=top0 ;  bottom != top ; )
     
133.     {
     
134.         ++gMax;
     
135.                 cout << "No. " << gMax << " :   ";
     
136.                
     
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;
     
150.                
     
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.         }
     
160.        
     
161.         if ( gMax == gMin )
     
162.         {
     
163.                 delete [] bUsed;
     
164.                 return (gMax); // 上界 = 下界
     
165.         }
     
166.        
     
167.         // 尝试组数更小的方案
     
168.        
     
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.     }
     
178.        
     
179.         k = gMax - numOfBig;
     
180.        
     
181.         for ( maxV=_BOUND, i=bottom1; arr[i]<=maxV; ++i ) maxV /= arr[i] ;
     
182.        
     
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];  // 每一组乘积允许的最小值
     
189.        
     
190.         integer *pGV, *pB, q, r, c;
     
191.        
     
192.     pGV = new integer [gMax];     // 本组之后未分配的数的乘积
     
193.     pB = new integer [k];         // 界限参数（_BOUND的乘幂）
     
194.        
     
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;
     
198. 
     
199.         for ( top=top0, i=1; i<=numOfBig ; ++i, --top )
     
200.         {
     
201.                 pbuf[i * Lpro    ] = 1;
     
202.                 pbuf[i * Lpro + 1] = top;
     
203.                
     
204.                 ppro[i * Lpro    ] = 1;
     
205.                 ppro[i * Lpro + 1] = arr[top];
     
206.                
     
207.                 bUsed[top] = 1;
     
208.         }       
     
209.        
     
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.         }
     
230.        
     
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.         }
     
248.        
     
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;
     
256.        
     
257.         for ( i=numOfBig+1; i<gMax; ++i ) pmaxV[i * Lpro]  = _BOUND;
     
258.        
     
259.         pGV[numOfBig] = hollpro;       
     
260.        
     
261.         for ( gCur=gMax-1 ;  gCur >= gMin ;  --gCur ) // 组数循环
     
262.         {
     
263.                 for ( top=top1, i=bottom=bottom1; i<=top; ++i ) bUsed[i] = 0;
     
264.                
     
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;
     
270.                        
     
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;
     
277.                        
     
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.                                 }
     
291.                                
     
292.                                 if ( product >= minGV ) // 进入下一组
     
293.                                 {
     
294.                                         pbuf[g*Lpro] = k;
     
295.                                         pGV[g] = pGV[g-1] / (c = product);
     
296.                                        
     
297.                                         while ( bottom != top && bUsed[top] ) --top;
     
298.                                         while ( bottom != top && bUsed[bottom] ) ++bottom;                                       
     
299.                                        
     
300.                                         ++g;
     
301.                                         break;
     
302.                                 }
     
303. 
     
304.                                 // 生成下一个乘积
     
305.                                 do {
     
306.                                         j = bottom;
     
307.                                        
     
308.                                         do {
     
309.                                                 i = pbuf[g*Lpro+k];
     
310.                                                 bUsed[i] = 0;
     
311.                                                 --k;
     
312.                                                
     
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 );
     
322.                                        
     
323.                                         if ( k >= 1 )
     
324.                                         {
     
325.                                                 icur = --i;
     
326.                                                 maxV = pmaxV[g*Lpro+k];
     
327.                                                 product = ppro[g*Lpro+k];
     
328.                                                 break;
     
329.                                         }                                       
     
330.                                        
     
331.                                         --g; // 退回到上一组
     
332.                                        
     
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;
     
342.                                                
     
343.                                                 return (gCur+1);
     
344.                                         }
     
345.                                        
     
346.                                         k = pbuf[g*Lpro];
     
347.                                         minGV = pminGV[g];
     
348.                                        
     
349.                                 } while ( 1 ); // end of 生成下一个乘积                               
     
350.                                
     
351.                         } while ( 1 ); // end of 生成第 g 组乘积
     
352.                        
     
353.                 } // end of g 循环
     
354.                
     
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;
     
364.                
     
365.                 // 输出
     
366.                 cout << endl << "groups = " << gCur << endl;
     
367.                 for ( i=1 ;  i <= gCur ;  ++i )
     
368.                 {
     
369.                         cout << "No. " << i << " :   ";
     
370.                        
     
371.                         for ( k=pbuf[i*Lpro], j=1 ;  j <= k ;  ++j )
     
372.                                 cout << " " << arr[ pbuf[i * Lpro + j] ];
     
373.                                
     
374.                         cout << endl;
     
375.                 }
     
376.                 cout << endl;
     
377.                
     
378.         } // end of 组数循环
     
379.        
     
380.         delete [] pB;
     
381.         delete [] pGV;
     
382.         delete [] pminGV;
     
383.         delete [] ppro;
     
384.         delete [] pmaxV;
     
385.         delete [] pbuf;
     
386.         delete [] bUsed;
     
387.        
     
388.         return (gMin);
     
389. }

复制代码

gxqcn

这么说来，我给出的程序效率是很高的，结果也是相当不错的。
谢谢你的代码，有空时我琢磨一下。

前面第26#说了，该问题更注重输出结果，因为是拿它作应用的；
即便运行时间长点也不碍事，反正只要运行一次。

当然，若有更优化的通用算法，则是上上品了。

无心人

为什么不用对数？
仅仅是因为是浮点运算？

假设某组数字的对数和为s
s <= 32
32 - s <= 1/16
是否算和优化的一组？

aimisiyou

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