算法题: best matching subsets

Question

我正在构建一个程序来匹配交易。以下是我目前面临的问题的描述。我需要一些算法方面的帮助。

给定两组具有相似属性(交易日期、账户、代码)的交易 A 和 B，我需要找到 A 中的交易 a 和 B 中的 b 的子集，其中 sum(a) 最接近 sum(b)。这里 sum() 是该子集的特定属性(净资金)的总和。需要最接近匹配的原因是，如果我们没有得到完美匹配(理想情况)，我们需要下一个最接近的匹配。注意:sum(a) 可以大于或小于 sum(b)。

我显然想在不使用生成 A 和 B 的所有组合并进行比较的蛮力方法的情况下执行此操作。

我觉得这可以通过一些动态编程方法来完成，但我无法提出任何具体的建议。非常感谢任何帮助。

Answer 1

这个问题是 NP 难的。

证明是子集和的缩减，这被称为 NP-hard。给定子集总和的任何实例，其中给定要求和的元素集合 S 和某个目标数 k，我们可以通过让 A 为集合 S 并让 B 为单例集 {k} 来构建问题的实例.如果我们解决你的问题并发现最接近的匹配并不完全是 k 的总和，那么我们就知道没有办法对 S 的子集求和得到 k。否则，如果有一种方法可以将 S 的元素相加到 k，那么匹配将完全等于 k，并且我们知道某个子集确实加起来等于目标。

因为这个问题是 NP-hard 问题，所以您不应该期待一个在多项式时间内运行的解决方案，或者比蛮力解决方案做得更好的解决方案。我认为您需要稍微放松一下问题才能获得好的结果。