algorithm - 根据需要转移值(value)的算法[保留]

Question

我需要一个算法，以最佳转移价值的基础上，需要的数额到其他帐户。例如，考虑到下面的帐户，什么是算法/psuedocode，可以在不导致正帐户不足的情况下，将有多余帐户的值转移到有不足帐户？
Account1 Balance: 0 Needed:.17853
Account2 Balance: 0 Needed:.1789524
Account3 Balance: 0.296 Needed:.4278
Account4 Balance: 0 Needed:.50231
Account5 Balance: 0.1 Needed:.17853
Account6 Balance: 0 Needed:.89
Account7 Balance: 4.0 Needed:0
Account8 Balance: 1.2447183721375 Needed:.894762

Answer 1

现在我假设你不需要知道钱从哪里来。（我们可以稍后处理）可以使用两个for循环：
第一个循环）遍历所有元素并收集多余的值。在您的示例中，这将导致帐户7的4个超额和帐户8的~0.3个超额，总计为4.3。
第二个循环）查看每个有缺陷的账户，从当前的超额价值中给出它所需要的，然后更新超额价值。在您的示例中，当您看到Account1需要.17时，您会给它那么多，然后将可用的超额部分从4.3更新到4.3-0.17=4.13。直到最后一个元素。
如果您想知道是谁解决了不足，那么在步骤1中，您应该收集一个具有超额价值的帐户列表，并在步骤2中更新该列表，而不是保留一个和并更新它。
同样，在您的情况下，列表将类似于（account 7，4.0）->（account 8，0.3），并且在尽可能长的时间使用account 7的步骤中，当它用完时，您将转到account 8。
时间复杂度为o（n）且为最优。