algorithm - 将传入和传出发票分组以使其总和为 0

Question

我今天遇到了一个有趣的问题，并决定用 C# 编写一个算法来解决它。

有总计为负的传入发票和总计为正的传出发票。任务是将这些发票分组，其中发票总数加起来恰好为 0。每个组可以包含无限个成员，因此如果有两个正数和一个负数成员但它们的总值为 0，则可以。

我们尝试最小化剩余发票总额的总和，并且根本没有其他限制。

我想知道这个问题是否可以追溯到一个已知问题，如果不能，那将是最有效的方法。天真的方法是将传入和传出发票分成两个不同的组，按总数排序，然后尝试一张一张地添加发票，直到达到零或符号已更改。然而，这假设一组中的发票应该大致相同，这是不正确的(一张巨大的进货发票可以与 10 个较小的出货发票相对)

有什么想法吗？

Answer 1

您面临的问题是一个众所周知且经过研究的问题，称为 The Subset Sum Problem .

不幸的是，问题是NP-Complet e，所以没有已知的多项式解¹。
事实上，甚至没有已知的多项式解法来确定这样的子集(即使是单个子集)是否存在，更不用说找到它了。

但是，如果您的输入包含相对较小(绝对值)的整数，则有一个非常有效的(伪多项式)dynamic programming solution可以用来解决问题。

如果不是这种情况，一些其他选择是:

1. 使用像 brute force 这样的指数解(您可以使用 branch and bound 技术对其进行优化)
2. 启发式解决方案，例如 Steepest Ascent Hill Climbing或 Genethic Algorithm s.
3. Approximation algorithm小号

---

(1) 大多数计算机科学研究人员认为不存在，这基本上是 P VS NP Problem .