Найдите способ минимизировать максимальную разницу - PullRequest
Новая
       45

Найдите способ минимизировать максимальную разницу

0 голосов
/ 07 октября 2018

N людям нужна различная сумма денег, указанная как: X_i (1 <= i <= N) </em> Но у нас есть фиксированные деньги, обозначенные 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)

Любые интересные ссылки также приветствуются на эту тему.

Ответы [ 2 ]

0 голосов
/ 07 октября 2018

Это можно решить за один проход после упорядочения суммы долга по убыванию.Долг выплачивается сверху вниз.Этот код 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
0 голосов
/ 07 октября 2018

Это можно решить с помощью жадного подхода.

Во-первых, обратите внимание, что начальные желаемые суммы также являются начальными различиями между требуемыми и заданными деньгами (потому что вы дали 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] и т. Д.

Конечно, при реализации алгоритма вы нена самом деле нужно отдавать монеты одну за другой, но это общее представление о том, что вы должны делать.

...