Подтвердить что ты не робот

Кто должен, кто оптимизирует деньги

Скажите, что у вас есть русские люди, каждый из которых обязан друг другу деньгами. В общем случае должно быть возможно уменьшить количество транзакций, которые должны иметь место. т.е. если X равно Y £ 4, а Y равно X £ 8, то Y нужно только заплатить X £ 4 (1 транзакция вместо 2).

Это становится сложнее, когда X должен Y, но Y должен Z, которому также нужен X. Я вижу, что вы можете легко вычислить один конкретный цикл. Это помогает мне, когда я думаю об этом как о полностью связанном графе, причем ребра - это сумма, которой должен обладать каждый человек.

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

Edit:

Цель этой проблемы состояла бы в том, чтобы иметь в системе бухгалтерского учета то, что может сказать каждому человеку при входе в систему. "Вы можете удалить M транзакций, просто заплатив кому-то сумму X, а кому-то сумму Y". Следовательно, решение банка (хотя и оптимальное, если все платят одновременно) не может быть действительно использовано здесь.

4b9b3361

ОТВЕТЫ

Ответ 1

Требуется ли людям очистить свои долги, заплатив кому-то, что они фактически должны деньги лично? Если нет, то, похоже, работает с подозрительной легкостью:

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

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

Предполагая, что я что-то пропустил, каковы ограничения, которые применяются (или грубая ошибка)?

Ответ 2

Назначьте одного человека произвольно, чтобы стать банкиром.

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

Будет максимум (n-1) транзакций, что довольно мало. Это быстро. Это просто.

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

* Исключение составляет сам банкир. Быстрая оптимизация заключается в том, чтобы назначенный банкир не тот, кто занимает нейтральную позицию.

** Далее объясним мою верхнюю границу:

Предположим, что оптимальный случай A дает $1 B, а C дает $1 D, а E нейтрально = две транзакции.

Затем с этой логикой, если E - назначенный банкир, A дает от 1 до E, E дает от 1 до B, C дает от 1 до E и E дает от 1 до D = четыре транзакции.

С оптимизацией, убедившись, что вы не выбрали нейтрального человека для банкира, выберите A вместо этого. A дает от 1 до B, C дает от 1 до A. A дает от $1 до D = три транзакции.

Ответ 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://settleup.destil.cz/report.pdf

Ответ 4

for each debt in debts
  debt.creditor.owed -= debt.amount
  debt.deptor.owed += debt.amount
end

for each person in persons
  if person.owed > 0 then
    deptors.add person
  else if person.owed < 0 then
    creditors.add person
  end
end

deptors.sort_by_owed_desc
creditor.sort_by_owed_asc

for each debtor in deptors
  while debtor.owed > 0
    creditor = creditors.top
    amount = min( debtor.owed, -creditor.owed)
    creditor.owed += amount
    debtor.owed -= amount
    if creditor.owed == 0 then
      creditors.remove_top
    end
    write debtor.name " owes " creditor.name " " amount "€"
  end
end

Ответ 5

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

Ответ 6

Здесь я использовал решение Python; это та же идея, что и сообщение Gunner, с несколькими изменениями строки:

for i in N:
    for j in N:
        if i!=j and owes[i][j] > owes[j][i]:
            owes[i][j] -= owes[j][i]
            owes[j][i] = 0
for k in N:
    for i in N:
        for j in N:
            if k == i or i == j or k == j:
                continue
            if owes[j][k] > owes[i][j]:
                owes[i][k] += owes[i][j]
                owes[j][k] -= owes[i][j]
                owes[i][j] = 0;

Работает с удовольствием.

Вы можете проверить его с помощью i.e.:

owes = [[0,2,11], [4,0,7], [2,3,0]]
N = range(len(owes))

Ответ 7

Я думаю, вам нужно создать другую структуру данных (дерево, каждый раз, когда один человек является корнем node), который будет проверять для каждого человека, сколько "транзакций" вы можете "убить", чем выбрать лучший один, сделайте цикл и перестройте его снова. Это не o (N), я думаю, что это N ^ 2, но это не даст вам лучшего результата. это просто стратегия.

Ответ 8

Эта проблема может быть решена с помощью алгоритма Варшалла.

for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    if ( i!= j && owes[i][j] > owes[j][i] )
owes[i][j] -= (owes[i][j] - owes[j][i]), owes[j][i] = 0;

for(k=0;k<n;k++)
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
  {
if( k == i || i == j || k == j ) continue;
if ( owes[j][k] > owes[i][j] )
{
int diff = owes[j][k] - owes[i][j]; 
owes[i][j] = 0;
owes[i][k ] += diff;
owes[j][k] -= diff;
} 
}

После завершения алгоритма общее количество требуемых транзакций будет состоять из числа положительных записей в таблице owes.

Я еще не проверял, будет ли алгоритм работать, исходя из природы проблемы, с которой он может работать. Решение равно O (N ^ 3).

Ответ 9

Я думаю, вы должны удалить все cicles, уменьшающие ребра, с минимальным значением края и удалениями со значением 0. После этого вы получите график с cicles. Я думаю, вы должны найти вершины, у которых нет указателей на них (человек, который должен только другим деньгам). Этот человек должен платить деньги, милый, никто не заплатит за них деньги. Поэтому я хочу сказать, что вы должны как-то найти, кому они должны платить.

Ответ 10

У меня есть решение проблемы, написанной в Matlab. Он основан на матрице того, кто должен кому. Число в (i, j) означает, что человек j должен человеку я номер. Например.

B означает A 2 и A a B 1

конечно, в этом случае тривиально, что B должен просто дать A 1

Это становится более сложным с большим количеством записей. Однако, с алгоритмом, который я написал, я могу гарантировать, что происходит не более N-1 транзакций, где N - это количество персонажей 2 в этом случае.

Вот код, который я написал.

function out = whooweswho(matrix)
%input sanitation
if ~isposintscalar(matrix)
    [N M] = size(matrix);
    if N ~= M
        error('Matrix must be square');
    end

    for i=1:N
        if matrix(N,N) ~= 0
            error('Matrix must have zero on diagonals');
        end
    end
else
    %construction of example matrix if input is a positive scalar
    disp('scalar input: Showing example of NxN matrix randomly filled');
    N = matrix;
    matrix = round(10*N*rand(N,N)).*(ones(N,N)-eye(N))
end

%construction of vector containing each persons balance
net = zeros(N,1);
for i=1:N
  net(i) = sum(matrix(i,:))-sum(matrix(:,i));
end

%zero matrix, so it can be used for the result
matrix = zeros(size(matrix));

%sum(net) == 0 always as no money dissappears. So if min(net) == 0 it
%implies that all balances are zero and we are done.
while min(net) ~= 0
  %find the poorest and the richest.
  [rec_amount reciever] = max(net);
  [give_amount giver] = min(net);
  %balance so at least one of them gets zero balance.
  amount =min(abs(rec_amount),abs(give_amount));
  net(reciever) = net(reciever) - amount;
  net(giver) = net(giver) + amount;
  %store result in matrix.
  matrix(reciever,giver) = amount;
end
%output equivalent matrix of input just reduced.
out = matrix;

конец