一个简单的算法问题.....(100分)

tdKno · 2002-05-22

在一个整数集合中X{Xi}(i=1....n),给定一个整数M,
要求在集合X中找出任意值组合之和最接近M的组合.
例如:X{1,2,3,4,5,6} M=5
2+3=5,
5,
1+4=5

maming · 2002-05-22

穷举法最简单。

tanhua · 2002-05-22

穷举发好编程。但是数据多了会很慢。我想个方法，M-Xi=Y;Xi与Y是一种组合。这好想
也是穷举，嘿嘿

wddelphi · 2002-05-22

有序地产生集合（或将集合排序），那么元素构成的子集的范围就大大缩小了，
例如:X{1,2,3,4,5,6……,100} M=52，那么子集就是X1{1,……,51}，再用tanhua的方法，
可使集合范围再缩小1/2，因为 1+51=51+1=52，2+50=50+2=52……

jstkof · 2002-05-22

要找出所有符合条件的子集合吗？还是只找出一个？

lbylby · 2002-05-23

我的意见跟jstkof一样，假如全部的建议用穷举法，假如只找一个那就简单多了，

DarwinZhang · 2002-05-25

用回溯法，但很耗时间。
1.先排序,复杂度 O( n*log2

)
2.回溯查找,复杂度 O( n! )

Pc 狂迷 · 2002-05-25

奇+奇=偶
偶+偶=偶
奇+偶=奇
范围再小一点。

creation-zy · 2002-06-05

http://www.delphibbs.com/delphibbs/dispq.asp?lid=1016791
稍加修改即可
ps:这个问题并不算简单

yinjie99 · 2002-06-09

穷举法很笨，
可用回溯法。可参看《算法分析基础》华中的

张剑波 · 2002-07-31

多人接受答案了。