从集合中选择特定数量的元素以达到某个值的算法

Question

给定一组元素 n[1]、n[2]、n[3]、.... n[x] 和一个数字 V。(元素有自己的值)

我想找到满足以下条件的所有元素组合:

1)每个组合包含特定数量的元素(例如:恰好 5 个元素)

Combination#1: n[1], n[2], n[21], n[22], n[24]

Combination#2: n[1], n[2], n[12], n[15], n[33]

......

2)组合中元素值的总和必须小于给定的数字 V(例如 V = 100)

Combination#1: n[1] + n[2] + n[21] + n[22] + n[24] < 100

Combination#2: n[1] + n[2] + n[12] + n[15] + n[33] < 100

......

我正在尝试编写一个计算这些元素的 C# 程序。但是语言并不重要，任何满足这些条件的算法都是可以接受的!

谢谢

Answer 1

由于无论如何您都可能不得不使用蛮力，因此您可以使用以下方法解决您的问题:

首先，对您的输入集 S 进行排序。

然后从S中移除所有大于V - 4*|min|的元素(其中|min|是最小元素的绝对值)，因为无论如何，它们不会出现在您的任何解决方案中。根据您的具体问题说明，此优化可能会进一步改进。

现在您生成 S 中元素的所有长度 C 的总和，从可能的最小数字开始(记住 S 是排序的)。

如果结果小于 V，将其添加到您的解决方案集中并增加最后一个被加数。

否则，将先前增加的被加数和该被加数之后的所有被加数设置为它们的最小可能值，并增加之前的被加数。

如果所有被加数都达到可能的最高值，您可以停止。你可能可以在那之前停下来，由于我的英语草率，这留给读者作为练习。