有效重新分配可变金额

Question

我有这个问题，我得到了n个账户，每个账户存储用户净资产的百分比。我必须将其从当前发行版移动到用户输入的发行版。为了实际转移资金，我称之为方法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次转账。

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

不过，有一点是肯定的：我们希望将所有超额费用都转为赤字。