algorithm - 可以使用什么算法找到最佳解决方案？

Question

我的账户有正负余额，有的之间有质押关系。质押使余额为负的账户有权从质押账户中取回资金以弥补损失。

我想找到调用此取款权的最佳顺序。

            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 的最佳解决方案。

这种优化问题怎么称呼，解决它的算法有哪些？

Answer 1

基本上是网络流量问题。我将为您的示例绘制容量图(未标记的弧具有无限容量)。 s 是源，t 是汇。

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

答案不是最大流量；它是使 1、然后 2、然后 3 最大化的流量。一种多时间算法是修改基于扩充路径(简单路径!——否则我们可能会从更高优先级的帐户中获取流量)优先扩充路径的最大流量算法通过 1，然后 2，然后 3。