找到正确数字集合的算法

Question

我可以接受用Python或C#的解决方案。

我有大约200个数字：

 19.16 
 98.48 
 20.65 
 122.08 
 26.16 
 125.83 
 473.33 
 125.92 
 3,981.21 
 16.81 
 100.00 
 43.58 
 54.19 
 19.83 
 3,850.97 
 20.83 
 20.83 
 86.81 
 37.71 
 36.33 
 6,619.42 
 264.53 
...
...

我知道在这组数字中，有一些数字的组合加起来会等于一个特定的数字，假设是2341.42。

我该如何找出哪些数字的组合加起来等于这个数呢？

我正在帮助一个会计找出正确的数字。

Answer 1

你可以使用回溯法来生成所有可能的解决方案。这样你就可以快速写出你的解决方案。

编辑：

你只需要用C#来实现这个算法：

public void backtrack (double sum, String solution, ArrayList numbers, int depth, double targetValue, int j)
{
    for (int i = j; i < numbers.Count; i++)
        {
            double potentialSolution = Convert.ToDouble(arrayList[i] + "");
            if (sum + potentialSolution > targetValue)
                continue;
            else if (sum + potentialSolution == targetValue)
            {
                if (depth == 0)
                {
                    solution = potentialSolution + "";
                    /*Store solution*/
                }
                else
                {
                    solution += "," + potentialSolution;
                    /*Store solution*/
                }
            }
            else
            {
                if (depth == 0)
                {
                    solution = potentialSolution + "";
                }
                else
                {
                    solution += "," + potentialSolution;
                }
                backtrack (sum + potentialSolution, solution, numbers, depth + 1, targetValue, i + 1);
            }
        }
}

你可以这样调用这个函数：

backtrack (0, "", numbers, 0, 2341.42, 0);

这段源代码是为了回答你的问题临时写的，没有经过测试，但从这段代码中你大致可以理解我的意思。

Answer 2

这里有一个用Python写的递归函数，它可以找到所有大小的解决方案，只需要你提供两个参数。

def find_all_sum_subsets(target_sum, numbers, offset=0):
    solutions = []
    for i in xrange(offset, len(numbers)):
        value = numbers[i]
        if target_sum == value:
            solutions.append([value])
        elif target_sum > value:
            sub_solutions = find_all_sum_subsets(target_sum - value, numbers, i + 1)
            for sub_solution in sub_solutions:
                solutions.append(sub_solution + [value])
    return solutions

下面是它的运行效果：

>>> find_all_sum_subsets(10, [1,2,3,4,5,6,7,8,9,10,11,12])
[[4, 3, 2, 1], [7, 2, 1], [6, 3, 1], [5, 4, 1], [9, 1], [5, 3, 2], [8, 2], [7, 3], [6, 4], [10]]
>>>

Answer 3

[开始编辑]:

我误解了原来的问题。我以为问题是问在200多个数字中，有没有4个数字的组合加起来等于另一个数字。其实不是这样，所以我的回答并没有太大帮助。

[结束编辑]

这个方法虽然有点笨重，但如果你只需要找到4个数字加起来等于某个特定值，它应该是有效的（它可能会找到超过4个的组合）：

首先，把你的200个数字放到一个数组里（或者列表，或者其他类似的结构）。然后你可以使用我之前发的代码。如果你的数字是写在纸上的，你需要像下面这样手动输入到数组里。如果你有电子版的数字，可以直接复制粘贴，然后在它们周围加上 numbers[x] = xxx 的代码。或者，你也可以把它们复制到一个文件里，然后从磁盘读取这个文件到数组中。

  double [] numbers = new numbers[200];
  numbers[0] = 123;
  numbers[1] = 456; 

  //
  // and so on.
  //

  var n0 = numbers;
  var n1 = numbers.Skip(1);
  var n2 = numbers.Skip(2);
  var n3 = numbers.Skip(3);

  var x = from a in n0
          from b in n1
          from c in n2
          from d in n3
          where a + b + c + d == 2341.42
          select new { a1 = a, b1 = b, c1 = c, d1 = d };

  foreach (var aa in x)
  {
    Console.WriteLine("{0}, {1}, {2}, {3}", aa.a1, aa.b1, aa.c1, aa.d1 );
  }