哪种算法可以用来寻找这个问题的最优解？

Question

哪种算法可以用来寻找这个问题的最优解？

4

我有一些账户，其中既有正余额也有负余额，并且有一些账户之间存在抵押关系。抵押关系使得那些有负余额的账户有权从抵押账户中取回资金来弥补亏损。

我想要找到最佳的顺序来行使这种取回资金的权利。

            1    2    3
A 1000 | -1000 -500 -500
B 1000 | -1000

在给定的例子中，账户A和B的余额为1000，账户1、2、3按优先级进行覆盖（1 > 2 > 3）。我想通过在1、2、3上分配A和B的资金来尽可能多地覆盖账户，同时遵守优先级。

在这个特定的例子中，选择A1作为我的第一对只会覆盖1000，但如果我选择B1、A2、A3，则可以获得覆盖2000的最佳解决方案。

这种优化问题被称为什么，有哪些算法可以解决它？

- OliverS

1

如果您在问题中解释会计术语，您将获得更多答案。承诺，不足和覆盖是什么意思？ - japreiss

也许你可以在http://cstheory.stackexchange.com或http://math.stackexchange.com找到更好的答案。 - sehe

我非常确定cstheory可以轻松回答这个问题，但这个问题不是该网站的主题。他们只接受研究级别的问题。 - OliverS

2个回答

2

我的协会说如果应用于几何领域以外的"Packing Problems"，你可能可以在该领域找到相关信息。

作为非该领域专家，我发现以下主题似乎相关：

或许甚至还有相关的内容：

http://en.wikipedia.org/wiki/Fragmentation_(computer)

- sehe

是的，我有同样的感觉，但希望能找到更好的匹配。 - OliverS

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Per · Accepted Answer

这基本上是一个网络流问题。我会为您的示例绘制容量图（未标记的弧具有无限容量）。s是源，t是汇。

     >A------->1
1000/ |\       ^\
   /  | \     /  \1000
  /   |  \   /    \
 /    |   \ /  500 v
s     |    /->2--->t
 \     \  /        ^
  \     \/        /
   \    /\       /500
1000\  /  \     /
     >B    --->3

答案不是最大流量，而是优先最大化1、2、3流量的流量。一种多项式时间算法是在基于增广路径的最大流算法中进行修改（只使用简单路径！否则可能从更高优先级的账户中取走流量），优先通过1、2、3增广路径来增加流量。