algorithm - 查找需要排除以匹配预期总和的求和问题的项

Question

我正在尝试自动化/加速控制过程。

想象这就像一个小商店的最佳方式：我知道应该在一天结束时留在收银机中的总数（例如 150 美元），我有一个销售清单，其总和显然应该匹配我们每天的总数。然而，该列表有时包含错误，例如错误的销售。

举个例子，假设预期总和为 150 美元，但我们的 10 次销售总和为 153.37 美元。现在，如果列表中有一个正好是 3.37 美元的销售，那很可能是错误的，我希望我的程序建议排除这个。

现在对于我的现实世界问题，“幸运的是”我的总和有更多的小数位数，建议意外排除错误销售的可能性非常低。另一方面，我通常处理多达 250 笔销售，其中通常多达 20 笔可能是错误的（因此仅考虑限制认为 sales(n) =<250 和 wrong trades(k) =<20）。

换句话说，我有一个集合 S {}。通过从集合中排除元素，S 中元素的总和应该与已知的总和 A 匹配，可以假设对此有唯一的解决方案（所以没有“你可以排除元素 B 或简单地排除元素 D AND E [as B = E+D])

如果这是要解决的“已知”问题，如果您能给我一个提示，在哪里可以找到合适的文献，我也会很高兴。

标签： algorithmmathsetcombinationssubset-sum

Answer 1

I believe you're just looking for combinations.

I would first calculate the difference: diff = sum(sales_list) - register_total

Then, filter the sales list for all elements in the set less than or equal to the difference: possibly_wrong_sales = sales list[ sales_list <= diff ]

Then find all possible combinations (and hopefully there is just 1) in the list/array of possibly_wrong_sales such that their sum equals that difference. That question has been answered here before, and answered very well too! The accepted answer includes full algorithms in lots of programming languages: Finding all possible combinations of numbers to reach a given sum

In literature, this is commonly referred to as the Coin Change Problem.