我有一个十进制数字(我们称它为目标)和一个其他十进制数字的数组(我们称其为数组元素)，我需要找到从元素求和到目标的所有数字组合。
我偏爱使用C＃(.Net 2.0)解决方案，但最好的算法可能会赢得胜利。
您的方法签名可能类似于：
1
| public decimal[][] Solve(decimal goal, decimal[] elements) |
有趣的答案。感谢您提供的指向Wikipedia的指针-虽然很有趣-但实际上并没有解决我在寻找完全匹配项时所说的问题-与传统的装箱/背包问题相比，更多的是会计/账簿平衡问题。
我一直在关注堆栈溢出的开发，并想知道它的用处。这个问题在工作中出现，我想知道堆栈溢出是否可以比我自己编写更快地提供现成的答案(或更好的答案)。也感谢您提出的建议将此作业标记为作业的评论-鉴于上述情况，我认为这是相当准确的。
对于那些感兴趣的人，这是我使用递归的解决方案(自然地)，我也改变了对方法签名的看法，并选择了List>而不是decimal [] []作为返回类型：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| 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++);
}
}
}
} |
如果您希望某个应用程序测试其工作原理，请尝试以下控制台应用程序代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| 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();
}
} |
我希望这可以帮助其他人更快地获得答案(无论是用于家庭作业还是其他)。
干杯...
通过动态编程可以解决子集和问题以及稍微更普遍的背包问题：不需要所有组合的强力枚举。请查阅Wikipedia或您最喜欢的算法参考。
尽管问题是NP完全的，但它们非常"容易" NP完全。元素数量的算法复杂度很低。
我认为您的手上有一个装箱问题(这很难解决NP)，所以我认为唯一的解决方案是尝试所有可能的组合，直到找到可行的组合。
编辑：正如评论中指出的那样，您不必总是为遇到的每组数字尝试每种组合。但是，您想出的任何方法都有最坏情况的数字集，您将必须尝试每种组合-或至少有一个组合子集会随该组的大小呈指数增长。
否则，这将不是NP难题。
在不解决暴力破解问题(如其他人已经提到的问题)的同时，您可能希望先对数字进行排序，然后再对剩余的数字进行排序(因为一旦传递了总和值，就不能添加比目标大的数字-和)。
这将改变实现算法的方式(以便仅排序一次，然后跳过标记的元素)，但平均而言会提高性能。
您已经描述了背包问题，唯一真正的解决办法是蛮力。有些近似解决方案速度更快，但可能无法满足您的需求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| 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);
}
} |
