Quién debe quién optimización de dinero

Question

Digamos que tiene n gente, cada uno que se debe dinero el uno al otro. En general, debería ser posible reducir la cantidad de transacciones que deben llevarse a cabo. es decir, si X debe Y £ 4 y Y debe X £ 8, entonces Y solo tiene que pagar X £ 4 (1 transacción en lugar de 2).

Esto se vuelve más difícil cuando X le debe a Y, pero Y le debe a Z quién también debe X. Veo que puedes calcular fácilmente un ciclo en particular. Me sirve de ayuda cuando lo veo como un gráfico completamente conectado, con los bordes como la cantidad que cada persona debe.

Parece que el problema es NP-completo, pero ¿qué tipo de algoritmo de optimización podría hacer, sin embargo, para reducir el total de cantidad de transacciones? No tiene que ser tan eficiente, ya que N es bastante pequeño para mí.

Editar:

El propósito de este problema sería la de poder tener en el sistema contable algo que se puede decir a cada persona cuando se conectan "Se puede quitar cantidad M de transacciones simplemente pagar a alguien X cantidad y otra persona Y cantidad ". Por lo tanto, la solución bancaria (aunque es óptima si todos pagan al mismo tiempo) realmente no se puede usar aquí.

Answer 1

Creo que necesitas construir una estructura de datos diferente (un árbol, cada vez que una persona es el nodo raíz) que verificará para cada persona cuántas "transacciones" puedes "matar", entonces, elige la mejor , haga el ciclo y vuelva a construirlo. No es o (N), creo que es N^2, y no le dará el mejor resultado. es solo una estrategia.

Answer 2

¿Se requiere que la gente salde sus deudas pagando a alguien a quien realmente le deben dinero personalmente? Si no, lo siguiente parece funcionar de manera sospechosamente fácil:

Para cada persona, calcula la cantidad neta que deberían pagar o deberían recibir.

Haga que alguien que deba dinero neto pague a alguien que debe recibir dinero neto mínimo (monto adeudado, monto a recibir). Después de esto, al menos uno de los dos participantes no debe nada y no debe recibir nada, por lo que puede ser eliminado del problema.

Suponiendo que he omitido algo, ¿cuáles son las restricciones que se aplican (o se ha cometido un error grave)?

Answer 3

Solo de pensarlo comenzaría mirando cada ciclo en el gráfico dirigido y reduciendo cada borde en el ciclo por el valor del borde mínimo en el ciclo, luego eliminé por completo el borde mínimo. Enjuague y repita.

Answer 4

Nomine a una persona arbitrariamente para ser el banquero.

Cada otra persona transfiere a esa persona la suma de todas las transacciones salientes menos las transacciones entrantes (por lo tanto, deposita o retira).

Habrá un máximo de (n-1) transacciones, que es bastante pequeño. Es rápido. Es simple.

Dado que todo el que transfiere el dinero tendrá que estar involucrado en una transacción de todos modos *, está delimitada a ser dos veces en el peor caso óptimo. **

* La excepción es el banquero sí mismos. Una optimización rápida es asegurar que el banquero designado no sea alguien que tenga una posición neutral.

** Explicando mi lógica límite superior más allá:

Supóngase el caso óptimo es A da $ 1 a B, y C da $ 1 a D, y E es neutral = dos transacciones.

Luego, con esta lógica, si E es el banquero designado, A otorga $ 1 a E, E da $ 1 a B, C da $ 1 a E y E da $ 1 a D = cuatro transacciones.

Con la optimización, asegurándose de no elegir una persona neutral para banquero, seleccione A en su lugar. A da $ 1 a B, C da $ 1 a A. A da $ 1 a D = tres transacciones.

Answer 5

Este problema se puede abordar con el algoritmo de Warshall.

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; 
} 
} 

Después de que los acabados de algoritmo, el número total de transacciones requeridas sería el número de entradas positivas en el le debe tabla.

No he verificado aún si el algoritmo funcionará, de acuerdo con la naturaleza del problema, puede funcionar. La solución es O (N^3).

Answer 6

Creo que debe eliminar todos los bordes reductores de cicles por un valor de borde mínimo y quitarlos con un valor 0. Después de esto, obtendrá un gráfico sin moverlos. Creo que debes encontrar vértices, que no tienen indicadores para ellos (el del hombre, que le debe dinero a los demás). Este hombre debe pagar dinero, porque no hay nadie para pagarles el dinero. Así que mi punto es que debes encontrar de alguna manera a quién deben pagar.

Answer 7

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 

Answer 8

Aquí está la solución de Python que utilicé; es la misma idea que la publicación de Gunner, con algunos cambios de línea:

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; 

Funciona como un regalo.

Puede probarlo con .: es decir

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

Answer 9

tengo una solución para el problema escrito en Matlab. Se basa en una matriz de quién debe quién. El número en (i, j) significa que la persona le debe a la persona el número. P.ej.

B debe A 2 y A debe B1

por supuesto, en este caso es trivial que B sólo debe dar un 1

Esto se hace más complejo, con más entradas. Sin embargo, con el algoritmo que escribí puedo garantizar que no ocurra más que transacciones N-1 donde N es el número de personas 2 en este caso.

Aquí está el código que escribí.

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; 

final

Answer 10

He creado una aplicación para Android que resuelve este problema. Puede ingresar los gastos durante el viaje, incluso le recomienda "quién debe pagar a continuación". Al final calcula "quién debe enviar cuánto a quién".Mi algoritmo calcula mínimo requerido número de transacciones y se puede configurar la "tolerancia transacción" que puede reducir las transacciones aún más (que no se preocupan por $ 1 transacciones) Inténtelo hacia fuera, se llama Settle Up:

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

Descripción de mi algoritmo:

Tengo un algoritmo básico que resuelve el problema con n-1 transacciones, pero no es óptimo. Funciona así: de los pagos, calculo el saldo para cada miembro. El saldo es lo que pagó menos lo que debería pagar. Ordeno miembros de acuerdo al equilibrio cada vez más. Entonces siempre tomo a los más pobres y ricos y se realiza una transacción. Al menos uno de ellos termina con saldo cero y se excluye de los cálculos posteriores. Con esto, el número de transacciones no puede ser peor que n-1. También minimiza la cantidad de dinero en las transacciones. Pero no es óptimo, porque no detecta subgrupos que puedan establecerse internamente.

Encontrar subgrupos que puedan establecerse internamente es difícil. Lo resuelvo generando todas las combinaciones de miembros y comprobando si la suma de saldos en el subgrupo es igual a cero. Comienzo con 2 pares, luego 3 pares ... (n-1) pares. Implementaciones de generadores de combinación están disponibles. Cuando encuentro un subgrupo, calculo las transacciones en el subgrupo usando el algoritmo básico descrito anteriormente. Para cada subgrupo encontrado, una transacción se salva.

La solución es óptima, pero la complejidad aumenta a O (n!). Esto se ve terrible, pero el truco es que habrá solo un pequeño número de miembros en la realidad. Lo he probado en Nexus One (procesador de 1 Ghz) y los resultados son: hasta 10 miembros: < 100 ms, 15 miembros: 1 s, 18 miembros: 8 s, 20 miembros: 55 s. Entonces, hasta 18 miembros, el tiempo de ejecución es bueno. Una solución para> 15 miembros puede ser utilizar solo el algoritmo básico (es rápido y correcto, pero no óptimo).

Código Fuente:

El código fuente está disponible dentro de un informe sobre el algoritmo escrito en Checa. El código fuente se encuentra al final y está en Inglés:

http://settleup.destil.cz/report.pdf