algorithm - 数组区分逻辑

Question

0K，问题就在这里，我会尽量说清楚。

因此，我们有一个键值对数组，格式为 unique id => number。

伪码数组A=array(0 => 17, 1 => 26, 2 => 17, 3 => 2, 4 => 7, 5 => 8);

我们看到数字的总数是 60。这总是正确的，所以数组 A 中的总数总是正确的。

现在我们有数组 B 在数组 B 中，也是唯一的 id => 值对，但这里有些值是假的/不正确的，总计(数组 B)-总计(数组 A)必须为 0。

即对于上面的示例数组 A= array(6 => 22, 7 => 11, 8 => 8, 9 => 9, 10 => 5, 11 => 10, 12 => 7, 13 => 17, 14 => 10);

现在，数组 B 总数为 99。60-99=-39，这意味着我们必须从数组 B 中找到等于 39 的所有数字组合。在这种情况下，只看 @eye 似乎只有 2这些组合是可能的:唯一 ID 10、12、13、14 不正确，或者 10、11、12、13 是假的/不正确的 (5+7+17+10=39)。现在，有了这么小的数组，很容易找到它们，使用循环并遍历所有可能的选项，但数组范围为数千(唯一 ID)。做这个的最好方式是什么？计算机如何最快找到假/不正确的对？

此外，我还欠给出最佳(和好的)答案的人一杯啤酒。

Answer 1

now, array B total is 99. 60-99=-39, which means we have to find all of the combinations of numbers that equal 39 from array B.

只有当您知道所有错误的数字都应该为零时，这才是正确的。

数组中的任何或所有数字都可能导致错误，因为错误数量的总和为 39。

话虽这么说，找到与特定总和相加的数字列表的子集的问题与 Subset Sum problem 有关。 ，虽然问题的正常陈述只是验证这样一个子集的存在，而你正在寻找所有这样的子集的列表。

我认为对于大型集合不存在有效的解决方案，并且蛮力解决方案呈指数级增长。