Algorithme pour partager/régler les dépenses entre un groupe

Question

Je suis impatient de trouver un algorithme pour le problème ci-dessous. Problème: Il y aura un ensemble de personnes qui se doivent de l'argent ou pas du tout. Maintenant, j'ai besoin d'un algorithme (le meilleur et le meilleur) pour régler les dépenses parmi ce groupe.

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

Maintenant, les frais par personne est 1500/3 = 500. Signification B pour donner A 100 B pour donner C 400. Je sais, je peux commencer par le moins passé et avancer les travaux. Est-ce que quelqu'un peut me pointer le meilleur si vous avez.

Merci d'avance.

En résumé, 1. Trouvez le total des dépenses et des dépenses par tête.
2. Trouvez le montant que chacun doit ou doit payer (-vous notez en circulation).
3. Commencez avec le minimum + ve. Attribuez-le au montant -ve.
4. Continuez à répéter l'étape 3 jusqu'à ce que vous n'ayez plus de temps.
s. Aller au prochain + numéro suivant. Continuez à répéter 3 & 4 jusqu'à ce qu'il y ait + ve nombres.

Ou y at-il une meilleure façon de faire? Je suis juste curieux. :)

Answer 1

Vous l'avez déjà décrit. Additionnez toutes les dépenses (1500 dans votre cas), divisez par le nombre de personnes partageant la dépense (500). Pour chaque individu, déduisez les contributions que cette personne a faites de la part individuelle (pour la personne A, déduisez 400 de 500). Le résultat est le net que cette personne "doit" au pool central. Si le nombre est négatif pour une personne, la piscine centrale "doit" à la personne. Puisque vous avez déjà décrit la solution, je ne sais pas ce que vous demandez. Peut-être que vous essayez de résoudre le problème sans la piscine centrale, la «banque»?

Je ne sais pas non plus ce que vous entendez par «commencer avec le montant le moins dépensé et aller de l'avant».

Answer 2

Le meilleur moyen de revenir à l'état zéro (nombre minimum de transactions) a été couvert dans cette question here.

Answer 3

Straightforward, comme vous le faites dans votre texte:

frais de retours à Payées par tout le monde dans le tableau original. Valeurs négatives: cette personne récupère un peu

Remettez tout ce que vous devez à la ligne suivante, puis retirez-la. Si vous en avez, attendez le deuxième tour. Une fois terminé, inversez le tout. Après ces deux tours, tout le monde a payé le même montant.

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; 

Answer 4

J'ai créé une application Android qui résout ce problème. Vous pouvez saisir des dépenses pendant le voyage, il vous recommande même "qui devrait payer ensuite". À la fin, il calcule "qui devrait envoyer combien à qui".Mon algorithme calcule nombre minimum requis de transactions et vous pouvez configurer la « tolérance de transaction » qui peut réduire les transactions encore plus loin (vous ne se soucient pas de 1 $ transactions) Essayez, il appelle Settle Up:

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

Description de mon algorithme:

J'ai un algorithme de base qui résout le problème avec n-1 transactions, mais ce n'est pas optimal. Cela fonctionne comme ceci: De paiements, je calcule l'équilibre pour chaque membre. L'équilibre est ce qu'il a payé moins ce qu'il devrait payer. Je trier les membres en fonction de l'équilibre de plus en plus. Ensuite, je prends toujours les plus pauvres et les plus riches et la transaction est faite. Au moins l'un d'entre eux se retrouve avec un solde nul et est exclu des autres calculs. Avec cela, le nombre de transactions ne peut pas être pire que n-1. Il minimise également la quantité d'argent dans les transactions. Mais ce n'est pas optimal, car il ne détecte pas les sous-groupes qui peuvent s'installer en interne.

Il est difficile de trouver des sous-groupes qui peuvent s'installer en interne. Je le résous en générant toutes les combinaisons de membres et en vérifiant si la somme des soldes dans le sous-groupe est égale à zéro. Je commence par 2 paires, puis 3 paires ... (n-1) paires. Les implémentations de générateurs combinés sont disponibles. Quand je trouve un sous-groupe, je calcule les transactions dans le sous-groupe en utilisant l'algorithme de base décrit ci-dessus. Pour chaque sous-groupe trouvé, une transaction est épargnée.

La solution est optimale, mais la complexité augmente jusqu'à O (n!). Cela semble terrible mais l'astuce est qu'il y aura juste un petit nombre de membres dans la réalité. Je l'ai testé sur Nexus One (processeur 1 Ghz) et les résultats sont: jusqu'à 10 membres: < 100 ms, 15 membres: 1 s, 18 membres: 8 s, 20 membres: 55 s. Donc jusqu'à 18 membres le temps d'exécution est bien. Une solution de contournement pour> 15 membres peut être d'utiliser seulement l'algorithme de base (c'est rapide et correct, mais pas optimal).

code source:

Le code source est disponible à l'intérieur d'un rapport sur l'algorithme écrit en tchèque. Le code source est à la fin et il est en anglais:

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

Answer 5

L'idée (semblable à ce qui est demandé mais avec une torsion/en utilisant un peu de concept de grand livre) est d'utiliser la piscine compte où pour chaque projet de loi, Les membres paient pour le compte du pool ou du pool. par exemple. en dessous de l'image ci-jointe, les frais Costco sont payés par M. P et a besoin de 93,76 $ de la piscine et les autres membres paient 46,88 $ à la piscine.

Answer 6

J'ai récemment écrit a blog post décrivant une approche pour résoudre le règlement des dépenses entre les membres d'un groupe où potentiellement tout le monde doit tout le monde, de sorte que le nombre de paiements nécessaires pour régler les dettes est le moins possible . Il utilise une formulation de programmation linéaire. Je montre également un exemple utilisant un petit paquet R qui implémente la solution.