algorithm - 可变金额的有效再分配

Question

我遇到了这个问题，我得到了 n 个帐户，每个帐户都存储了用户净 Assets 的一定百分比。我必须将它从当前分布移动到用户输入的分布。为了真正转移资金，我调用了方法 moveMoney(initialAcct, finalAcct, amnt)，我必须尽可能少地调用它。

这看起来像是一个经典的算法问题，但没有想到如何解决它。好像有点像打包优化，但是我好像搞不懂。

Answer 1

考虑何时至少有两种方法可以弥补任何一个帐户中的缺失金额，但选择一种方法比另一种方法更有好处。例如，

index:  0  1  2  3  4  5  6  7
input:  0  1  6  3  4  0  0  0
target: 7  0  0  0  0  1  1  5
needed: 7 -1 -6 -3 -4  1  1  5

如果我们选择用 (1, 6) 覆盖数量 7，我们得到

amount    index
     1 -> 0
     6 -> 0
     3 -> 5
     1 -> 6 // from index 5 to 6
     1 -> 7 // from index 5 to 7
     4 -> 7

6 次转移。

而如果我们选择用 (3, 4) 覆盖数量 7，我们得到

amount    index
     3 -> 0
     4 -> 0
     1 -> 5
     6 -> 6
     5 -> 7 // from index 6 to 7

5 次转移。

因此我们可以看到，对于任何一个状态，当我们转换到输出时，我们可能需要考虑所有可能的精确覆盖。在某种程度上，不同的超额会导致更多的州具有潜在的精确覆盖，即使是创建过渡性超额的选择也不能保证可以互换。

但有一件事是肯定的:我们希望将所有超额转为不足。