查找大小为 n 的列表中的哪些数字与另一个数字相加的算法
-
01-07-2019 - |
题
我有一个十进制数(我们称之为 目标)和其他十进制数的数组(我们称该数组为 元素)并且我需要找到来自的所有数字组合 元素 总和就是目标。
我更喜欢 C# (.Net 2.0) 中的解决方案,但无论如何,最好的算法可能会获胜。
您的方法签名可能类似于:
public decimal[][] Solve(decimal goal, decimal[] elements)
解决方案
有趣的答案。感谢您对维基百科的指点 - 虽然很有趣 - 他们实际上并没有解决我在寻找精确匹配时所说的问题 - 更多的是会计/账簿平衡问题而不是传统的装箱/背包问题。
我一直饶有兴趣地关注堆栈溢出的发展,并想知道它会有多大用处。这个问题在工作中出现,我想知道堆栈溢出是否可以比我自己编写更快地提供现成的答案(或更好的答案)。也感谢建议将此标记为家庭作业的评论 - 我想鉴于上述情况,这是相当准确的。
对于那些感兴趣的人,这是我的解决方案,它使用递归(自然)我也改变了对方法签名的想法,并选择 List> 而不是十进制[][]作为返回类型:
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();
}
}
我希望这可以帮助其他人更快地得到答案(无论是家庭作业还是其他)。
干杯...
其他提示
子集和问题以及稍微更一般的背包问题可以通过动态规划来解决:不需要对所有组合进行强力枚举。请查阅维基百科或您最喜欢的算法参考。
虽然这些问题是 NP 完全问题,但它们是非常“简单”的 NP 完全问题。元素数量的算法复杂度较低。
我想你有一个 装箱问题 在你的手上(这是 NP 难的),所以我认为唯一的解决方案是尝试每一种可能的组合,直到找到一个有效的组合。
编辑:正如评论中指出的,你不会 总是 必须尝试 每一个 组合为 每一个 你遇到的一组数字。然而,您提出的任何方法都有最坏情况场景的数字集,您可以在其中 将要 必须尝试 每一个 组合——或者至少是随着集合大小呈指数增长的组合子集。
否则,它就不是NP困难的了。
你已经描述了一个 背包问题, ,唯一真正的解决方案是暴力。有一些更快的近似解决方案,但它们可能无法满足您的需求。
虽然没有解决暴力问题(正如其他人已经提到的),但您可能想首先对数字进行排序,然后检查剩下的可能的数字(因为一旦您传递了 Sum 值,您就不能添加任何大于 Goal 的数字 -和)。
这将改变您实现算法的方式(以便仅排序一次,然后跳过标记的元素),但平均而言会提高性能。
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);
}
}