知道和找表格中的相加数！再次求救！

safejkp

首先在新的一年里面恭祝大家新年快乐，身体健康，多多的赚钱啊。有个老问题请大家帮忙解决！

       前几次发了几个贴求助，xiangchendub都无私的帮我解决的了。真的非常的感谢他！
可惜女友的上司老是要我们帮他解决一样的问题，这不又来了一组数据，气得我们不知道怎么办！
这次不知道他是想凑个数出来，还是忘记了哪些相加数。
只好再一次厚脸皮的请求xiangchendub帮忙！也希望知道的大侠们帮忙。
烦劳大侠们，帮忙找出那些相加数！
问题简述：已经知道表格中29个数据，也知道由这个表格中的几个（未知个数）数据相加而成的和，要找出是那些数据相加而成这个和。

name004

这种类型未接触过，规划求解？关注学习

dg831451

楼主给的这个数据里面我用规划求解过.但是这29位再怎么凑合都不能得到你所要的404034.3这个结果的.所以呢这个404034.3不可能是这29个数的某一些数加起来的结果
而且我用规划求解用了大概20分钟的时间也只能求出一个相近的结果,而且这29个数当中还要变一些数才行.

[ 本帖最后由 dg831451 于 2009-1-1 14:50 编辑 ]

xiangchendub

兄弟，元旦都不休息呀，给你两组解。

1. 12128
   
2. 12133
   
3. 13000
   
4. 13000
   
5. 15485.4
   
6. 19680.5
   
7. 20674.9
   
8. 24880.5
   
9. 25000
   
10. 25256
    
11. 29877.1
    
12. 33992
    
13. 43500
    
14. 50797.6
    
15. 64629.3

复制代码

1. 1001
   
2. 1398
   
3. 10345
   
4. 12133
   
5. 13000
   
6. 13000
   
7. 13000
   
8. 13000
   
9. 13000
   
10. 15068.6
    
11. 15485.4
    
12. 15717.8
    
13. 24880.5
    
14. 25256
    
15. 29877.1
    
16. 33992
    
17. 34710.6
    
18. 54540
    
19. 64629.3

复制代码

happy new year you guys!

dg831451

楼上的厉害,我规划求解算了20分钟没有算出来,不知道楼上的是如何算出来的,是否也用规划求解?

xiangchendub

回楼上，不是用excel做的，用MAPLE + GAUSS + GAMS 做的。
excel的规划求解解决整数规划用branch and bound运算，
这样分支太多了，所以速度很慢，也不容易精确。

regards

dg831451

原来如此,我说吗.我算了20多分钟没有找到一个解呢,兄弟你元旦不也是没有休息吗?外面的人太多了,去哪里都不方便,还不如上网学习一下呢

xiangchendub

呵呵，是呀，上网也是一种消遣。

To name004: 短信收到。
这种问题，到目前为止还没有通用的解决办法，因为它是NP-Hard problem,
谁都没有好办法，除非 NP= P. 我是这样做的,仅供参考。

1.reduce lattice basis (中文不知道叫啥)
   用maple做的，LLL 算法是比较流行的，也可以参照seysen的算法。
   说白了就是把数据集减少，剔除出去一些不太可能用到的数。

2. 做最大可能性估计。
    就是估计哪些数组成目标值的可能性大。比如在这个例子中
    13000几乎是必须出现的，然后把这些出现几率大的数挑出来。
    这步用GAUSS做的。

3. 利用求解软件或优化软件求解。
     可以利用类似于 excel规划求解的功能，找出符合要求的数字。
     我用GAMs 做的。

大致上就是这样，当然解决此类问题，还有很多种方法，比如
GA 等等启发式算法，但都要多试几次。

Regards

safejkp

真是太感谢大家了，过节还帮我解决问题！xiangchendub 亲个

香川群子

xiangchendub 发表于 2009-1-1 16:01
呵呵，是呀，上网也是一种消遣。

To name004: 短信收到。

这位也是人才……

不过结论被我推翻了，楼主的问题用我的凑数程序可以很快得到答案。秒级