算法找到正确的数字集
我将采用c＃解决方案的python
我有大约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
我怎样才能找出哪些数字组合会加起来呢？
我正在帮助会计人员跟踪正确的数字
[开始编辑]：
我误读了原来的问题。 我认为它表示在200多个数字的列表中有4个数字的组合，这些数字加起来与其他数字相加。 这不是所要求的，所以我的回答并没有多大帮助。
[结束编辑]
这非常笨重，但是如果您只需要找到加起来一定值的4个数字（它可以找到超过4个元组），它应该可以工作：
只需将200个数字放入数组（或列表或某些IEnumerable结构）中，然后就可以使用我发布的代码了。 如果您在纸上有数字，则必须手动将它们输入到arrays中，如下所示。 如果你在软拷贝中使用它们，你可以剪切并粘贴它们，然后在它们周围添加数字[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 ); }
您可以使用回溯来生成所有可能的解决方案。 这样您就可以快速编写解决方案。
编辑：
你只需在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);
源代码是动态实现的，以回答您的问题，但没有经过测试，但从本质上说，您可以理解我的意思。
这是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]] >>>
如果找到任意两（2）个数字的组合，请尝试以下方法：
float targetSum = 3; float[] numbers = new float[]{1, 2, 3, 4, 5, 6}; Sort(numbers); // Sort numbers in ascending order. int startIndex = 0; int endIndex = numbers.Length - 1; while (startIndex != endIndex) { float firstNumber = numbers[startIndex]; float secondNumber = numbers[endIndex]; float sum = firstNumber + secondNumber; if (sum == targetSum) { // Found a combination. break; } else if (sum < targetSum) { startIndex++; } else { endIndex--; } }
请记住，使用浮点数或十进制数时，舍入可能是个问题。
这应该作为递归算法实现。 基本上，对于任何给定的数字，确定是否存在剩余数字的子集，其总和是您期望的值。
遍历数字列表; 对于每个条目，从总计中减去该值，并确定是否存在剩余列表的一个子集，该子集总计为新总计。 如果没有，请尝试使用原始总数和列表中的下一个数字（当然还有一个较小的子列表）。
至于实现：您希望定义一个方法，该方法采用目标编号和列表，并返回总计到该目标编号的数字列表。 该算法应该遍历列表; 如果从目标数中减去的列表元素为零，则返回列表中的该元素; 否则，使用列表的其余部分和新目标编号递归方法。 如果任何递归返回非null结果，则返回; 否则，返回null。
ArrayList FindSumSubset(decimal sum, ArrayList list) { for (int i = 0; i < list.Length; i++) { decimal value = list[i]; if (sum - value == 0.0m) { return new ArrayList ().Add(value); } else { var subset = FindSumSubset(sum - value, list.GetRange(i + 1, list.Length -i); if (subset != null) { return subset.Add(value); } } } return null; }
但是请注意，这个顺序非常难看，对于数量要大得多的数组，这相对较快就变得棘手了。 不过，这应该可以在小于200的小数的地质时间内完成。