我今天遇到了一个有趣的问题，决定用 C# 编写一个算法来解决它。
存在总计为负的传入发票和总计为正的传出发票。任务是对这些发票进行分组，其中发票的总和恰好为 0。每个组可以包含无限的成员，因此如果有两个正成员和一个负成员，但它们的总值(value)为 0，也没关系。
我们尝试最小化剩余发票总额的总和，并且根本没有其他限制。
我想知道这个问题是否可以追溯到已知问题，如果不是，这将是最有效的方法。天真的方法是将传入和传出发票分成两个不同的组，按总数排序，然后尝试一张一张地添加发票，直到达到零或符号发生变化。然而，这假设一组中的发票应大致相同，但事实并非如此(一张巨大的传入发票可以与 10 张较小的传出发票相对应)
有什么想法吗？
最佳答案
您面临的问题是众所周知且经过研究的问题，称为 The Subset Sum Problem 。
不幸的是，问题是NP-Complet e，因此没有已知的多项式解1。
事实上，没有已知的多项式解来确定这样的子集(甚至是单个子集)是否存在，更不用说找到它了。
但是，如果您的输入由相对较小(绝对值)的整数组成，则有一个非常有效的(伪多项式)dynamic programming solution可以用来解决问题。
如果不是这种情况，一些其他替代方案是:
- 使用指数解，如 brute force (您也许可以使用 branch and bound 技术对其进行优化)
- 启发式解决方案，例如 Steepest Ascent Hill Climbing或Genethic Algorithm
- Approximation algorithm s
(1) 大多数计算机科学研究人员认为不存在，这基本上就是 P VS NP Problem .
关于algorithm - 将传入和传出发票分组，使其总和为 0，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16831322/