我有一个十进制数字(我们称其为 Goal )和一个其他十进制数字的数组(我们称为数组 elements ),并且我需要找到从总和到目标的 元素中 所有数字的组合。
我偏爱使用C#(.Net 2.0)解决方案,但最好的算法可能会赢得胜利。
您的方法签名可能类似于:
public decimal[][] Solve(decimal goal, decimal[] elements)
有趣的答案。感谢您提供的指向Wikipedia的指针-尽管很有趣-但实际上并没有解决我在寻找精确匹配时所指出的问题- 与传统的装箱/背包问题相比,更多的是会计/账簿平衡问题。
我一直关注着堆栈溢出的发展,想知道它的用处。这个问题在工作中出现,我想知道堆栈溢出是否可以比我自己编写更快地提供现成的答案(或更佳的答案)。也感谢您提出的建议将此作业标记为作业的评论- 鉴于上述情况,我认为这是相当准确的。
对于那些有兴趣的人,这是我的使用递归的解决方案(自然地),我也改变了对方法签名的看法,并选择了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++); } } } }
如果您希望某个应用程序测试其工作原理,请尝试以下控制台应用程序代码:
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(); } }
我希望这可以帮助其他人更快地得到答案(无论是用于家庭作业还是其他)。
干杯…