Алгоритм распределения / распределения расходов между группами

Question

Я с нетерпением жду алгоритма для решения проблемы ниже.

Проблема: Будет множество людей, которые должны друг другу деньги или нет. Теперь мне нужен алгоритм (лучший и аккуратный) для расчета расходов среди этой группы.

Person AmtSpent
------ ---------
A       400  
B      1000  
C       100  
Total  1500

Теперь расходы на одного человека составляют 1500/3 = 500. То есть, B, чтобы дать A 100. B, чтобы дать C 400. Я знаю, я могу начать с наименьшей потраченной суммы и работать вперед.

Может кто-нибудь указать мне лучший, если у вас есть.

Заранее спасибо.

Подводя итог, 1. Найдите общие расходы и расходы на душу населения.
2. Найдите сумму, которую каждый должен или непогашен (-ve обозначает непогашенную).
3. Начните с наименьшей суммы + ve. Выделите его на сумму -ve.
4. Продолжайте повторять шаг 3, пока не закончится сумма -ve.
s. Перейти к следующему большему + ве число. Продолжайте повторять 3 и 4, пока не появятся цифры + ve.

Или есть лучший способ сделать? Мне просто интересно. :)

Answer 1

В этом вопросе рассмотрен лучший способ возврата к нулевому состоянию (минимальное количество транзакций) здесь .

Answer 2

Я создал приложение для Android, которое решает эту проблему. Вы можете ввести расходы во время поездки, он даже рекомендует «кто должен платить дальше». В конце он вычисляет «кто должен кому сколько отправлять». Мой алгоритм вычисляет минимально необходимое количество транзакций, и вы можете установить «допуск транзакций», который может еще больше сократить транзакции (вам не нужны транзакции в 1 доллар). Попробуйте, это называется Settle Up:

https://market.android.com/details?id=cz.destil.settleup

Описание моего алгоритма:

У меня есть базовый алгоритм, который решает проблему с n-1 транзакциями, но он не оптимален. Это работает так: Из платежей я вычисляю баланс для каждого участника. Баланс - это то, что он заплатил, минус то, что он должен заплатить. Я сортирую членов по балансу все чаще. Тогда я всегда беру самых бедных и самых богатых и сделка совершается. По крайней мере один из них заканчивается нулевым балансом и исключается из дальнейших расчетов. При этом количество транзакций не может быть хуже, чем n-1. Это также минимизирует количество денег в транзакциях. Но это не оптимально, потому что он не обнаруживает подгруппы, которые могут располагаться внутри.

Найти подгруппы, которые могут обосноваться внутри, сложно. Я решаю это путем генерации всех комбинаций членов и проверки, равна ли сумма остатков в подгруппе нулю. Я начинаю с 2 пар, затем с 3 парами ... (n-1) пар. Доступны реализации комбинированных генераторов. Когда я нахожу подгруппу, я вычисляю транзакции в подгруппе, используя базовый алгоритм, описанный выше. Для каждой найденной подгруппы экономится одна транзакция.

Решение является оптимальным, но сложность возрастает до O (n!). Это выглядит ужасно, но хитрость в том, что в реальности будет только небольшое количество членов. Я протестировал его на Nexus One (процессор с частотой 1 ГГц) и получил следующие результаты: до 10 участников: <100 мс, 15 участников: 1 с, 18 участников: 8 с, 20 участников: 55 с. Так что до 18 членов время выполнения хорошо. Обходной путь для> 15 участников может заключаться в использовании только базового алгоритма (он быстрый и правильный, но не оптимальный).

Исходный код:

Исходный код доступен в отчете об алгоритме, написанном на чешском языке. Исходный код в конце и на английском языке:

http://www.settleup.info/files/master-thesis-david-vavra.pdf

Answer 3

Вы уже описали это. Суммируйте все расходы (1500 в вашем случае), разделите на количество людей, разделяющих расходы (500). Для каждого человека вычтите взносы, которые этот человек сделал из индивидуальной доли (для человека A вычтите 400 из 500) В результате получается, что человек «обязан» центральному пулу. Если число отрицательно для любого человека, центральный пул "должен" человеку.

Поскольку вы уже описали решение, я не знаю, о чем вы спрашиваете. Может быть, вы пытаетесь решить проблему без центрального пула, «банка»?

Я также не знаю, что вы подразумеваете под «начать с наименьшей суммы и продолжить работу».

Answer 4

Я недавно написал пост в блоге , описывающий подход к решению проблемы урегулирования расходов между членами группы, где потенциально каждый должен всем остальным, так что количество платежей, необходимых для погашения задолженности, является наименее возможный. Он использует формулировку линейного программирования. Я также показываю пример использования крошечного пакета R, который реализует решение.

Answer 5

Идея (похожая на ту, о которой спрашивают, но с концепцией скручивания / использования небольшого количества регистров) состоит в том, чтобы использовать учетную запись пула, где за каждый счет участники либо платят пулу, либо получают из пула. например на прилагаемом изображении расходы Costco оплачивает мистер П, и ему требуется 93,76 доллара от пула, а другие участники платят 46,88 доллара в пул.

Answer 6

Я бы хотел внести предложение об изменении основных параметров, с точки зрения UX, если вы не против ужасно.

Независимо от того, относятся ли его услуги или продукты к группе, иногда этими вещами можно поделиться. Например, закуска или частный / полуприватный сеанс на конференции.

Для таких вещей, как поднос с закусками, подразумевается, что у всех есть доступ, но не обязательно, чтобы у всех он был. Поручить каждому человеку разделить расходы, если, скажем, только 30% участников приняли участие в конфликте, когда дело доходит до разделения счета. Другие группы людей могут не заботиться вообще. Таким образом, с точки зрения алгоритма, вы должны сначала решить, какой из этих трех вариантов будет использоваться, вероятно, для каждого расхода:

Универсальное разбиение
Разделить на тех, кто принимал участие, равномерно
Разделить на пропорцию на участника

Я лично предпочитаю второй в целом, потому что у него есть полезность, чтобы обрабатывать полное владение расходами за расходы, используемые только одним человеком, некоторыми людьми и всей группой в целом. Это также устраняет этический вопрос о пропорциональных различиях с общим обобщением того, что, если вы принимаете участие, вы платите равномерное разделение независимо от того, сколько у вас на самом деле было. В качестве социального элемента я бы рассмотрел кого-то, у кого была «небольшая выборка» чего-то, чтобы просто попробовать, а затем решил, что больше не будет оправданием удалять этого человека из людей, разделяющих расходы.

Итак, small-sampling != partaking;)

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

Итак, в итоге вы берете свой список расходов и перебираете их с каждым человеком. В конце проверки индивидуальных расходов вы берете людей, которые приняли участие, и применяете равномерное разделение этих расходов к каждому человеку, и обновляете текущее разделение счета каждого участника.

Простите за псевдокод:

list_of_expenses[] = getExpenseList()
list_of_agents_to_charge[] = getParticipantList()

for each expense in list_of_expenses
    list_of_partakers[] = getPartakerList(expense)
    for each partaker in list_of_partakers
       addChargeToAgent(expense.price / list_of_partakers.size, list_of_agents_to_charge[partaker])

Затем просто переберите ваш list_of_agents_to_charge[] и сообщите каждый итог каждому агенту.

Вы можете добавить поддержку чаевых, просто рассматривая чаевые как дополнительные расходы в своем списке расходов.

Прошу прощения, если я полностью сошел с вас, ОП.

ps: Я бы хотел написать мобильное приложение, чтобы сделать это сейчас xD Вот что я получаю за проверку SO перед уходом с работы ...

Answer 7

Javascript решение принятого алгоритма:

const payments = {
  John: 400,
  Jane: 1000,
  Bob: 100,
  Dave: 900,
};

function splitPayments(payments) {
  const people = Object.keys(payments);
  const valuesPaid = Object.values(payments);

  const sum = valuesPaid.reduce((acc, curr) => curr + acc);
  const mean = sum / people.length;

  const sortedPeople = people.sort((personA, personB) => payments[personA] - payments[personB]);
  const sortedValuesPaid = sortedPeople.map((person) => payments[person] - mean);

  let i = 0;
  let j = sortedPeople.length - 1;
  let debt;

  while (i < j) {
    debt = Math.min(-(sortedValuesPaid[i]), sortedValuesPaid[j]);
    sortedValuesPaid[i] += debt;
    sortedValuesPaid[j] -= debt;

    console.log(`${sortedPeople[i]} owes ${sortedPeople[j]} $${debt}`);

    if (sortedValuesPaid[i] === 0) {
      i++;
    }

    if (sortedValuesPaid[j] === 0) {
      j--;
    }
  }
}

splitPayments(payments);

/*
  C owes B $400
  C owes D $100
  A owes D $200
*/

Answer 8

Прямо, как вы делаете в своем тексте:

Возвращает расходы, которые должны быть оплачены всеми в исходном массиве. Отрицательные ценности: этот человек получает обратно

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

procedure SettleDepth(Expenses: array of double);
var
  i: Integer;
  s: double;
begin
  //Sum all amounts and divide by number of people
  // O(n) 
  s := 0.0;
  for i := Low(Expenses) to High(Expenses) do
     s := s + Expenses[i];

  s := s / (High(Expenses) - Low(Expenses));

  // Inplace Change to owed amount
  // and hand on what you owe
  // drop out if your even 
  for i := High(Expenses) downto Low(Expenses)+1 do begin
     Expenses[i] := s - Expenses[i];
     if (Expenses[i] > 0) then begin
        Expenses[i-1] := Expenses[i-1] + Expenses[i];
        Expenses.Delete(i);
     end else if (Expenses[i] = 0) then begin
        Expenses.Delete(i);
     end;
  end;

  Expenses[Low(Expenses)] := s - Expenses[Low(Expenses)];
  if (Expenses[Low(Expenses)] = 0) then begin
     Expenses.Delete(Low(Expenses));
  end;

  // hand on what you owe
  for i := Low(Expenses) to High(Expenses)-1 do begin
     if (Expenses[i] > 0) then begin
        Expenses[i+1] := Expenses[i+1] + Expenses[i];
     end;
  end;
end;