问题描述
你会如何去测试添加的所有可能的组合从一组给定的数字，使他们加起来一个给定的最终数量？
How would you go about testing all possible combinations of additions from a given set of numbers so they add up to a given final number?
例如：
- 设置数增加：{1,5,22,15,0，...}
- 期望的结果：12345
PS：问这个问题，因为数学是不是我的专长，不知道如何能够适应于code
P.S: Asking this problem as maths isn't my forte and wondering how this could be adapted in code.
推荐答案
这问题可与所有可能的和过滤掉那些到达目标的递归组合来解决。这里是算法的Python：
This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print "sum(%s)=%s" % (partial, target)
if s >= target:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i+1:]
subset_sum(remaining, target, partial + [n])
if __name__ == "__main__":
subset_sum([3,9,8,4,5,7,10],15)
#Outputs:
#sum([3, 8, 4])=15
#sum([3, 5, 7])=15
#sum([8, 7])=15
#sum([5, 10])=15
这类型的算法相当不错，在以下
This type of algorithms are very well explained in the following Standford's Abstract Programming lecture - this video is very recommendable to understand how recursion works to generate permutations of solutions.
修改
下面是同一算法的Java版本：
Here is the Java version of the same algorithm:
package tmp;
import java.util.ArrayList;
import java.util.Arrays;
class SumSet {
static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
int s = 0;
for (int x: partial) s += x;
if (s == target)
System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
if (s >= target)
return;
for(int i=0;i<numbers.size();i++) {
ArrayList<Integer> remaining = new ArrayList<Integer>();
int n = numbers.get(i);
for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
partial_rec.add(n);
sum_up_recursive(remaining,target,partial_rec);
}
}
static void sum_up(ArrayList<Integer> numbers, int target) {
sum_up_recursive(numbers,target,new ArrayList<Integer>());
}
public static void main(String args[]) {
Integer[] numbers = {3,9,8,4,5,7,10};
int target = 15;
sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
}
}
有完全一样的试探法。我的Java是一个有点生疏，但我认为很容易理解。
It is exactly the same heuristic. My Java is a bit rusty but I think is easy to understand.
C＃转换的Java解决方案： （由@JeremyThompson）的
public static void Main(string[] args)
{
List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
int target = 15;
sum_up(numbers, target);
}
private static void sum_up(List<int> numbers, int target)
{
sum_up_recursive(numbers, target, new List<int>());
}
private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
int s = 0;
foreach (int x in partial) s += x;
if (s == target)
Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);
if (s >= target)
return;
for (int i = 0; i < numbers.Count; i++)
{
List<int> remaining = new List<int>();
int n = numbers[i];
for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);
List<int> partial_rec = new List<int>(partial);
partial_rec.Add(n);
sum_up_recursive(remaining, target, partial_rec);
}
}
红宝石的解决方案： （由@emaillenin）的
def subset_sum(numbers, target, partial=[])
s = partial.inject 0, :+
# check if the partial sum is equals to target
puts "sum(#{partial})=#{target}" if s == target
return if s >= target # if we reach the number why bother to continue
(0..(numbers.length - 1)).each do |i|
n = numbers[i]
remaining = numbers.drop(i+1)
subset_sum(remaining, target, partial + [n])
end
end
subset_sum([3,9,8,4,5,7,10],15)
编辑：复杂的讨论
正如其他人提到这是一个 NP问题。它可以在指数时间为O（2 ^ n）的可以解决，例如对于n = 10将有1024个可能的解决方案。如果你想达到的目标是在一个较低的范围内，那么这算法。因此，例如：
As others mention this is an NP problem. It can be solved in exponential time O(2^n), for instance for n=10 there will be 1024 possible solutions. If the targets you are trying to reach are in a low range then this algorithm works. So for instance:
subset_sum（[1,2,3,4,5,6,7,8,9,10]，100000）生成1024分支机构，因为目标永远不会变过滤掉可能的解决方案。
subset_sum([1,2,3,4,5,6,7,8,9,10],100000) generates 1024 branches because the target never gets to filter out possible solutions.
在另一方面 subset_sum（[1,2,3,4,5,6,7,8,9,10]，10）只产生175枝，因为目标达到 10 获取筛选出多种组合。
On the other hand subset_sum([1,2,3,4,5,6,7,8,9,10],10) generates only 175 branches, because the target to reach 10 gets to filter out many combinations.
如果 N 和目标都是大号码应该移动到该解决方案的大致版本。
If N and Target are big numbers one should move into an approximate version of the solution.
这篇关于求数的所有可能的组合，以达到给定的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！