最佳组合算法

bombzhao

假设有47，33，22，22，10，10，4.7，1这几个数，现在任意给定一个小于100的数，如何通过算法来求得在给定的几个数之间的组合最接近或等于这个数。例如：给定33，最佳的组合为33；
给定54，最佳的组合为22，22和10。

[ 本帖最后由 bombzhao 于 2006-9-10 10:14 编辑 ]

langue

没懂，是不是在数的集合里往大的找数字来加满一个值

bombzhao

现在题目应该已经比较清楚了吧？

langue

我好悲哀，看不懂。麻烦用英语翻译一下吧，或者把原题的文本或者出处告诉我。

目前我的理解：

假设有47，33，22，22，10，10，4，7，1这几个数供选择，现在任意给定一个小于100的正整数，如何通过算法来取得一种对应的组合，组合中可以有由供选择的数（可重复）作为选项，要求取得的这个组合计重复相加得到的值最接近或等于这个要求的数值。例如：给定33，最佳的组合为33；给定54，最佳的组合为22，22和10。

mingjwan

楼主的意思很明白了。看不懂，可以看楼主给出的例子啊。
但是具体怎么算。好像比较难，是不是所有的组合都得试一下啊。

望高手指点啊。

langue

原帖由 mingjwan 于 2006-9-10 11:40 发表
楼主的意思很明白了。看不懂，可以看楼主给出的例子啊。
但是具体怎么算。好像比较难，是不是所有的组合都得试一下啊。

望高手指点啊。

那你解释一下吧，我目前还没明白过来。

mingjwan

呵呵。就是从中找出几个数的和，离所给的数字最近啊。也就是差值的绝对值最小啊。
然后把这几个数字打出来。

langue

原帖由 mingjwan 于 2006-9-10 11:50 发表
呵呵。就是从中找出几个数的和，离所给的数字最近啊。也就是差值的绝对值最小啊。
然后把这几个数字打出来。

我有些理解了。谢谢。试试看先。

VirusCamp

背包问题？
NP 问题。

bombzhao

原帖由 VirusCamp 于 2006-9-10 12:45 发表
背包问题？
NP 问题。

呵呵，类似！