2

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

有总额为负的进货发票和总额为正的发货发票。任务是从这些发票中创建组，其中发票的总和正好为 0。每个组可以包含无限的成员，所以如果有两个正成员和一个负成员但它们的总值为 0，没关系。

我们试图最小化剩余发票总数的总和，并且根本没有其他约束。

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

有任何想法吗？

4

1 回答 1

4

您面临的问题是一个众所周知和研究过的问题，称为子集和问题。

不幸的是，问题是NP-Complet e，因此没有已知的多项式解决方案1。
事实上，甚至没有已知的多项式解决方案可以确定这样的子集（甚至是单个子集）是否存在，更不用说找到它了。

但是，如果您的输入由相对较小（绝对值）的整数组成，则有一个非常有效的（伪多项式）动态规划解决方案可用于解决该问题。

如果不是这种情况，其他一些替代方案是：

  1. 使用诸如蛮力之类的指数解决方案（您可以使用分支定界技术对其进行优化）
  2. 启发式解决方案，例如Steepest Ascent Hill Climbing或Genethic Algorithm s。
  3. 逼近算法

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

于 2013-05-30T08:42:44.027 回答