从集合中选择特定数量的元素以达到某个值的算法
给定一组元素 n[1], n[2], n[3], .... n[x] 和一个数字 V。（元素有自己的值）
我想找到满足以下条件的所有元素组合满足以下条件：
1) 每个组合包含特定数量的元素（例如：正好 5 个元素）
组合#1： n[1]、n[2]、n[21]、n[22]、n[24]
组合#2： n[1]、n[2]、n[12]、n[15]、n[33]
......
2) 组合中元素值的总和必须为小于给定数字 V（例如 V = 100）
组合#1： n[1] + n[2] + n[21] + n[22] + n[24] < 100
组合#2： n[1] + n[2] + n[12] + n[15] + n[33] < 100
......
我正在尝试编写计算这些元素的 ac# 程序。但语言并不重要，任何算法满足这些条件都是可以接受的！
谢谢
Given set of elements n[1], n[2], n[3], .... n[x] and a number V. (Elements have their own values)
I would like to find all combinations of elements which satisfies the following conditions:
1) Each combination contains specific number of elements (e.g: exactly 5 elements)
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) Sum of elements values in combination must be smaller than given number V (e.g 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
......
I am trying to write a c# program which computes these elements. But language is not important, any algorithm satisfies these conditions is acceptable!
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
由于无论如何您可能都必须使用暴力，因此您可以通过以下方法解决您的问题：
首先，对输入集 S 进行排序。
然后从 S 中删除所有大于
V - 4*|min 的元素|（其中|min|是最小元素的绝对值），因为它们无论如何都不会出现在您的任何解决方案中。根据您的具体问题规范，此优化可能会进一步改进。现在，您生成 S 中元素的所有长度为 C 的总和，从尽可能小的数字开始（请记住，S 是已排序的）。
如果结果小于 V，则将其添加到解集中并增加最后一个被加数。
否则，将之前增加的被加数以及该被加数之后的所有被加数设置为其可能的最小值，并增加之前增加的被加数。
如果所有被加数都达到了可能的最高值，您可以停止。你也许可以在此之前停下来，由于我的英语很蹩脚，所以这是留给读者的练习。
Since you will probably have to use brute force anyway, you can solve your problem with the following approach:
First of all, sort your input set S.
Then remove all elements from S which are greater than
V - 4*|min|(where|min|is the absolute value of the smallest element), because they won't appear in any of your solutions anyway. Depending on your exact problem specification, this optimization may be improved further.Now you generate all sums of length C of elements in S, starting with the smallest possible numbers (remember that S is sorted).
If the result is smaller than V, add it to your solution set and increase the last summand.
Otherwise, set the previously increased summand and all summands after that one to their smallest possible values and increase the summand just before that.
You can stop if all summands have reached their highest possible values. You may be able to stop long before that, which is left as an exercise to the reader due to my sloppy English.
我不太确定，但也许你可以调整这个想法，使其具有所有组合必须具有一定数量的元素的条件。
http://en.wikipedia.org/wiki/Knapsack_problem
然而，据说背包问题具有 NP 完全的复杂性，需要精确解决......这是个坏消息。所以人们建议做的是使用回溯算法。
我相信你会在google中找到很多关于背包问题回溯的代码。
我希望这有帮助
Im not so sure but maybe you can adapt this idea to have the condition that all combinations must have a certain amount of elements.
http://en.wikipedia.org/wiki/Knapsack_problem
However, it is said that the knapsack problem has a complexity of NP-complete to be solved exactly... That's bad news. So what people suggest to do, is using a backtracking algorithm.
I'm sure you will find a lot of codes in google about backtracking for the knapsack problem.
I hope this helps