收藏本站腾讯微博新浪微博

经典论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

蓝色理想 最新研发动态 网站开通淘帖功能 - 蓝色理想插件 论坛内容导读一页看论坛 - 给官方提建议

论坛活动及任务 地图和邮件任务 请多用悬赏提问 热夏来袭,选一款蓝色理想的个性T恤吧!

手机上论坛,使用APP获得更好体验 急需前端攻城狮,获得内部推荐机会 论坛开通淘帖功能,收藏终于可以分类了!

搜索
查看: 4429|回复: 4

求组合算法

[复制链接]
发表于 2006-7-2 18:44:00 | 显示全部楼层 |阅读模式
已知道1-33个数字里面任意取出6个数字的组合有1107568种(纸上算的。电脑上运行死机。)
每个组合中6个数字相加后,会出现相同的和,如何得到最多的相同和数目
比如:
1+2+3+4+5+12 = 27
2+3+4+5+6+7 = 27

有多少个组合的和是27?
最多的相同和是多少,有多少?

有没有好的思路?

发表于 2006-7-2 21:35:00 | 显示全部楼层
用循环枚举,进行算法优化后, P4 2.4G / 256M / WindowXP SP2 / IE6.0 运行 41s,平均 CPU 占用率在 40% 左右

结论:相同结果最多的应该分布在正中间: (1+2+3+4+5+6 + 28+29+30+31+32+33) / 2 = 102

代码:

 提示:您可以先修改部分代码再运行



结果:

  1. 1107568
  2. 21 : 1
  3. 22 : 1
  4. 23 : 2
  5. 24 : 3
  6. 25 : 5
  7. 26 : 7
  8. 27 : 11
  9. 28 : 14
  10. 29 : 20
  11. 30 : 26
  12. 31 : 35
  13. 32 : 44
  14. 33 : 58
  15. 34 : 71
  16. 35 : 90
  17. 36 : 110
  18. 37 : 136
  19. 38 : 163
  20. 39 : 199
  21. 40 : 235
  22. 41 : 282
  23. 42 : 331
  24. 43 : 391
  25. 44 : 454
  26. 45 : 532
  27. 46 : 612
  28. 47 : 709
  29. 48 : 811
  30. 49 : 930
  31. 50 : 1055
  32. 51 : 1202
  33. 52 : 1353
  34. 53 : 1528
  35. 54 : 1710
  36. 55 : 1916
  37. 56 : 2130
  38. 57 : 2372
  39. 58 : 2619
  40. 59 : 2896
  41. 60 : 3181
  42. 61 : 3495
  43. 62 : 3816
  44. 63 : 4170
  45. 64 : 4527
  46. 65 : 4918
  47. 66 : 5314
  48. 67 : 5741
  49. 68 : 6171
  50. 69 : 6635
  51. 70 : 7096
  52. 71 : 7591
  53. 72 : 8083
  54. 73 : 8604
  55. 74 : 9118
  56. 75 : 9663
  57. 76 : 10193
  58. 77 : 10751
  59. 78 : 11293
  60. 79 : 11856
  61. 80 : 12398
  62. 81 : 12962
  63. 82 : 13495
  64. 83 : 14046
  65. 84 : 14565
  66. 85 : 15094
  67. 86 : 15586
  68. 87 : 16088
  69. 88 : 16543
  70. 89 : 17004
  71. 90 : 17418
  72. 91 : 17830
  73. 92 : 18190
  74. 93 : 18549
  75. 94 : 18847
  76. 95 : 19141
  77. 96 : 19376
  78. 97 : 19599
  79. 98 : 19760
  80. 99 : 19912
  81. 100 : 19995
  82. 101 : 20068
  83. 102 : 20076
  84. 103 : 20068
  85. 104 : 19995
  86. 105 : 19912
  87. 106 : 19760
  88. 107 : 19599
  89. 108 : 19376
  90. 109 : 19141
  91. 110 : 18847
  92. 111 : 18549
  93. 112 : 18190
  94. 113 : 17830
  95. 114 : 17418
  96. 115 : 17004
  97. 116 : 16543
  98. 117 : 16088
  99. 118 : 15586
  100. 119 : 15094
  101. 120 : 14565
  102. 121 : 14046
  103. 122 : 13495
  104. 123 : 12962
  105. 124 : 12398
  106. 125 : 11856
  107. 126 : 11293
  108. 127 : 10751
  109. 128 : 10193
  110. 129 : 9663
  111. 130 : 9118
  112. 131 : 8604
  113. 132 : 8083
  114. 133 : 7591
  115. 134 : 7096
  116. 135 : 6635
  117. 136 : 6171
  118. 137 : 5741
  119. 138 : 5314
  120. 139 : 4918
  121. 140 : 4527
  122. 141 : 4170
  123. 142 : 3816
  124. 143 : 3495
  125. 144 : 3181
  126. 145 : 2896
  127. 146 : 2619
  128. 147 : 2372
  129. 148 : 2130
  130. 149 : 1916
  131. 150 : 1710
  132. 151 : 1528
  133. 152 : 1353
  134. 153 : 1202
  135. 154 : 1055
  136. 155 : 930
  137. 156 : 811
  138. 157 : 709
  139. 158 : 612
  140. 159 : 532
  141. 160 : 454
  142. 161 : 391
  143. 162 : 331
  144. 163 : 282
  145. 164 : 235
  146. 165 : 199
  147. 166 : 163
  148. 167 : 136
  149. 168 : 110
  150. 169 : 90
  151. 170 : 71
  152. 171 : 58
  153. 172 : 44
  154. 173 : 35
  155. 174 : 26
  156. 175 : 20
  157. 176 : 14
  158. 177 : 11
  159. 178 : 7
  160. 179 : 5
  161. 180 : 3
  162. 181 : 2
  163. 182 : 1
  164. 183 : 1
复制代码
回复 支持 反对

使用道具 举报

发表于 2006-7-3 00:20:00 | 显示全部楼层
二维动态规划

 提示:您可以先修改部分代码再运行

回复 支持 反对

使用道具 举报

 楼主| 发表于 2006-7-3 11:08:00 | 显示全部楼层
楼上的算法真快速
这具体的数(如:164)是怎么定义出来的

var dat = new Array(6);
dat[0] = new Array(34); dat[0][0] = 0;
dat[1] = new Array(64); dat[1][0] = 2;
dat[2] = new Array(92); dat[2][0] = 5;
dat[3] = new Array(118); dat[3][0] = 9;
dat[4] = new Array(142); dat[4][0] = 14;
dat[5] = new Array(164); dat[5][0] = 20;
回复 支持 反对

使用道具 举报

发表于 2006-7-3 12:00:00 | 显示全部楼层
这个其实只是为了节省空间而做的,似乎有点难理解.
其实那是一个hash表,序号是相加的和,值是次数.
因此,2个数相加,最小值是1+2=3,最大值是33+32=65.共65-3+1=63个数据
因为js的数组是从0开始的,所以用[0]记下1与最小值的差,用[1..63]做hash表
其余依此类推
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|小黑屋|Archiver|手机版|blueidea.com ( 湘ICP备12001430号 )  

GMT+8, 2020-9-30 08:55 , Processed in 0.093514 second(s), 10 queries , Gzip On, Memcache On.

Powered by Discuz! X3.2 Licensed

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表