Алгоритм распределения/расчета затрат среди группы

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

Я создал приложение для 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 Ghz procesor), и результаты: до 10 членов: < 100 мс, 15 членов: 1 с, 18 членов: 8 с, 20 членов: 55 с. Таким образом, до 18 членов время исполнения в порядке. Обходным решением для > 15 членов может быть использование только базового алгоритма (это быстро и правильно, но не оптимально).

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

Прямо, как и в тексте:

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

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

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;  

Ответ 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
*/

Ответ 8

Я хотел бы предложить изменить основные параметры с точки зрения 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[] свой list_of_agents_to_charge[] и сообщите каждый итог каждому агенту.

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

Извиняюсь, если я полностью сошел с вас, ОП.

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