找到最小化最大差异的方法

Question

N 个人需要不同数量的钱：X_i (1<=i <=N) 但是我们有固定货币，用 M 表示。有可能 M 少于满足每个人需要所需的总货币量。

我想找到一种分配资金 (M) 的方法，使所有人所需资金与给定资金之间的最大差异最小化。有办法吗？

  e.g : N = 4, M=3

  X1=5, X2=4, X3=2, X4=2

  In this case we should distribute like : 2 1 0 0 
  so difference array is : 3 3 2 2
  maximum difference is minimized (which is 3)

也欢迎任何有趣的link讨论这个话题。

Answer 1

这可以用贪婪的方法来解决。

首先，请注意初始期望金额也是所需金额和给定金额之间的初始差额（因为您已将 0 给每个人）。因此，对于您的示例，差异从 [5, 4, 2, 2].

开始

其次，请注意，在给定时间将钱给除具有最大差异的人以外的任何人都不会减少最大差异。例如，如果数组是 5, 4, 2, 2，给第一个人以外的任何人钱都不会减少最大差值：[5, 3, 2, 2], [5, 4, 1, 2 ], [5, 4, 2, 1]（最大差值保持在5）。

因此，您应该始终将一枚硬币给在给定点上具有最大差异的人（或者其中任何一个，如果有平局），直到您运行没有硬币：[5 , 4, 2, 2] -> [4, 4, 2, 2] -> [3, 4, 2, 2] -> [3, 3, 2, 2] -> [2, 3, 2, 2 ] -> [2, 2, 2, 2], 等等

当然，在实现算法的时候，其实并不需要一个一个给硬币，但这是你应该做的大体思路。

Answer 2

这可以在对债务金额降序排列后一次性解决。债务是从上到下偿还的。这个python代码应该说清楚了：

def get_max_debt_after_distribution(debt, money):

    if not debt:
        raise ValueError('Please specify debt')

    debt.sort(reverse=True)
    debt.append(0)  # Add zero debt to simplify algorithm

    for i in range(1, len(debt)):
        last_amount = debt[i-1]
        new_amount = debt[i]

        # To bring the max diff down from "last_amount" to "new_amount",
        # we need to pay the difference for each debt
        to_pay = (last_amount - new_amount) * i

        # Check if we have enough money to pay the full amount
        if to_pay <= money:
            money -= to_pay
        else:
            # Out of money. Remaining money goes to highest debts.
            return last_amount - int(money / i)

    # There was enough money to pay all the debt
    return 0

print(get_max_debt_after_distribution([5, 4, 2, 2], 3))  # prints 3
print(get_max_debt_after_distribution([5, 5, 5, 5], 7))  # prints 4

找到最小化最大差异的方法

Find a way to minimize max difference

arrays

sorting

greedy