C# 从大小为 n 的列表中找出哪些数字和另一个数字相加的算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/83547/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Algorithm to find which numbers from a list of size n sum to another number
提问by Sam Meldrum
I have a decimal number (let's call it goal) and an array of other decimal numbers (let's call the array elements) and I need to find all the combinations of numbers from elementswhich sum to goal.
我有一个十进制数（我们称之为目标）和一个其他十进制数的数组（我们称之为数组元素），我需要从总和到目标的元素中找到数字的所有组合。
I have a preference for a solution in C# (.Net 2.0) but may the best algorithm win irrespective.
我更喜欢 C# (.Net 2.0) 中的解决方案，但无论如何最好的算法可能会获胜。
Your method signature might look something like:
您的方法签名可能类似于：
public decimal[][] Solve(decimal goal, decimal[] elements)
采纳答案by Sam Meldrum
Interesting answers. Thank you for the pointers to Wikipedia - whilst interesting - they don't actually solve the problem as stated as I was looking for exact matches - more of an accounting/book balancing problem than a traditional bin-packing / knapsack problem.
有趣的答案。感谢您对维基百科的指点——虽然很有趣——他们实际上并没有像我在寻找精确匹配那样解决问题——更多的是会计/账簿平衡问题，而不是传统的装箱/背包问题。
I have been following the development of stack overflow with interest and wondered how useful it would be. This problem came up at work and I wondered whether stack overflow could provide a ready-made answer (or a better answer) quicker than I could write it myself. Thanks also for the comments suggesting this be tagged homework - I guess that is reasonably accurate in light of the above.
我一直很感兴趣地关注堆栈溢出的发展，并想知道它会有多大用处。这个问题在工作中出现，我想知道堆栈溢出是否可以比我自己编写的更快地提供现成的答案（或更好的答案）。也感谢建议将此标记为家庭作业的评论 - 我想根据上述情况，这是相当准确的。
For those who are interested, here is my solution which uses recursion (naturally) I also changed my mind about the method signature and went for List> rather than decimal[][] as the return type:
对于那些感兴趣的人，这是我的解决方案，它使用递归（自然地）我也改变了对方法签名的看法，并选择 List> 而不是 decimal[][] 作为返回类型：
public class Solver {
private List<List<decimal>> mResults;
public List<List<decimal>> Solve(decimal goal, decimal[] elements) {
mResults = new List<List<decimal>>();
RecursiveSolve(goal, 0.0m,
new List<decimal>(), new List<decimal>(elements), 0);
return mResults;
}
private void RecursiveSolve(decimal goal, decimal currentSum,
List<decimal> included, List<decimal> notIncluded, int startIndex) {
for (int index = startIndex; index < notIncluded.Count; index++) {
decimal nextValue = notIncluded[index];
if (currentSum + nextValue == goal) {
List<decimal> newResult = new List<decimal>(included);
newResult.Add(nextValue);
mResults.Add(newResult);
}
else if (currentSum + nextValue < goal) {
List<decimal> nextIncluded = new List<decimal>(included);
nextIncluded.Add(nextValue);
List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
nextNotIncluded.Remove(nextValue);
RecursiveSolve(goal, currentSum + nextValue,
nextIncluded, nextNotIncluded, startIndex++);
}
}
}
}
If you want an app to test this works, try this console app code:
如果您想要一个应用程序来测试它是否有效，请尝试以下控制台应用程序代码：
class Program {
static void Main(string[] args) {
string input;
decimal goal;
decimal element;
do {
Console.WriteLine("Please enter the goal:");
input = Console.ReadLine();
}
while (!decimal.TryParse(input, out goal));
Console.WriteLine("Please enter the elements (separated by spaces)");
input = Console.ReadLine();
string[] elementsText = input.Split(' ');
List<decimal> elementsList = new List<decimal>();
foreach (string elementText in elementsText) {
if (decimal.TryParse(elementText, out element)) {
elementsList.Add(element);
}
}
Solver solver = new Solver();
List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
foreach(List<decimal> result in results) {
foreach (decimal value in result) {
Console.Write("{0}\t", value);
}
Console.WriteLine();
}
Console.ReadLine();
}
}
I hope this helps someone else get their answer more quickly (whether for homework or otherwise).
我希望这有助于其他人更快地得到他们的答案（无论是家庭作业还是其他）。
Cheers...
干杯...
回答by Rob Dickerson
I think you've got a bin packing problemon your hands (which is NP-hard), so I think the only solution is going to be to try every possible combination until you find one that works.
我认为您的手上有一个装箱问题（这是 NP 难题），所以我认为唯一的解决方案是尝试所有可能的组合，直到找到一个可行的组合。
Edit: As pointed out in a comment, you won't alwayshave to try everycombination for everyset of numbers you come across. However, any method you come up with has worst-case-scenario sets of numbers where you willhave to try everycombination -- or at least a subset of combinations that grows exponentially with the size of the set.
编辑：正如评论中指出的那样，您不必总是为遇到的每一组数字都尝试每种组合。然而，你拿出任何方法有最坏情况的场景组数字，你的会必须尝试所有的组合-或者至少与集合的大小呈指数增长一个组合的子集。
Otherwise, it wouldn't be NP-hard.
否则，它不会是 NP-hard。
回答by ARKBAN
You have described a knapsack problem, the only true solution is brute force. There are some approximation solutions which are faster, but they might not fit your needs.
你描述了一个背包问题，唯一真正的解决方案是蛮力。有一些近似解决方案更快，但它们可能不适合您的需求。
回答by Steve Jessop
The subset-sum problem, and the slightly more general knapsack problem, are solved with dynamic programming: brute-force enumeration of all combinations is not required. Consult Wikipedia or your favourite algorithms reference.
子集和问题，以及稍微更一般的背包问题，用动态规划解决：不需要对所有组合进行暴力枚举。查阅维基百科或您最喜欢的算法参考。
Although the problems are NP-complete, they are very "easy" NP-complete. The algorithmic complexity in the number of elements is low.
尽管这些问题是 NP 完全的，但它们是非常“容易”的 NP 完全问题。元素数量的算法复杂度低。
回答by Adi
While not solving the problem of brute force (as others already mentioned) you might want to sort your numbers first, and then go over the possible ones left (since once you passed Sum value, you can't add any number larger than Goal - Sum).
虽然没有解决蛮力问题（正如其他人已经提到的），您可能希望先对数字进行排序，然后再检查剩下的可能的数字（因为一旦传递了 Sum 值，就不能添加任何大于目标的数字 -和）。
This will change the way you implement your algorithm (in order to sort only once and then skip marked elements), but on the average would improve performance.
这将改变您实现算法的方式（以便只排序一次然后跳过标记的元素），但平均而言会提高性能。
回答by guest
public class Logic1 {
static int val = 121;
public static void main(String[] args)
{
f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{");
}
static void f(int[] numbers, int index, int sum, String output)
{
System.out.println(output + " } = " + sum);
//System.out.println("Index value1 is "+index);
check (sum);
if (index == numbers.length)
{
System.out.println(output + " } = " + sum);
return;
}
// include numbers[index]
f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
check (sum);
//System.out.println("Index value2 is "+index);
// exclude numbers[index]
f(numbers, index + 1, sum, output);
check (sum);
}
static void check (int sum1)
{
if (sum1 == val)
System.exit(0);
}
}
