从大小为n的列表中找出哪些数字总和为另一个数字的algorithm
我有一个十进制数（让我们称之为目标 ）和一个其他十进制数字（让我们调用数组元素 ）的数组，我需要find所有数组的元素 ，总结到目标。
我喜欢C＃（.Net 2.0）中的解决scheme，但最好的algorithm可能会赢。
您的方法签名可能如下所示：
public decimal[][] Solve(decimal goal, decimal[] elements) 有趣的答案。 感谢您的指点维基百科 – 虽然有趣的是，他们并没有真正解决问题，因为我正在寻找确切的匹配 – 更多的会计/书籍的问题比传统的装箱/背包问题。
我一直在关注堆栈溢出的兴趣，并想知道它会是多么有用。 这个问题出现在工作中，我想知道堆栈溢出是否能够提供一个现成的答案（或更好的答案）比我自己写的更快。 也感谢意见，build议这被贴上作业 – 我想这是相当准确的，鉴于上述情况。
对于那些有兴趣的人来说，这里是我的解决scheme，它使用recursion（自然）我也改变了我的想法的方法签名和去作为返回types的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++); } } } }
如果你想要一个应用程序来testing这个作品，试试这个控制台应用程序代码
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(); } }
我希望这可以帮助别人更快地得到答案（无论是作业还是其他）。
干杯…
dynamic规划解决了子集总和问题和稍微更一般的背包问题：所有组合的强制枚举不是必需的。 请参阅维基百科或您最喜爱的algorithm参考。
虽然问题是NP完全的，但是它们是非常“容易的”NP-complete。 元素数量的algorithm复杂度较低。
我认为你手上已经有了一个装箱问题 （这是NP难题），所以我认为唯一的解决办法是尝试每种可能的组合，直到find一个可行的组合。
编辑：正如在评论中指出的，你不会总是尝试每 一个你遇到的数字组合。 然而，你提出的任何方法都有最坏情况下的数字集合，在这里你将不得不尝试每一种组合 – 或者至less是一组随着集合的大小呈指数增长的组合。
否则，这不会是NP难。
你已经描述了一个背包问题 ，唯一真正的解决scheme是蛮力。 有一些近似解决scheme更快，但可能不适合您的需求。
虽然没有解决蛮力问题（正如其他人已经提到过），但是您可能需要首先对数字进行sorting，然后再查看可能的数字（因为一旦您传递了总和值，就不能添加大于目标的数字 – 和）。
这将改变你实现algorithm的方式（为了只sorting一次，然后跳过标记的元素），但平均来说会提高性能。
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); } }
