Algorithme de partage / règlement des dépenses entre un groupe

Je suis à la recherche d'un algorithme pour le problème ci-dessous.

Problème: Il y aura un ensemble de personnes qui doivent les uns aux autres un peu d'argent ou aucun. Maintenant, j'ai besoin d'un algorithme (le meilleur et soigné) pour régler des dépenses au sein de ce groupe.

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

Maintenant, les dépenses par personne est 1500/3 = 500. Sens B pour donner Un 100. B pour donner C 400. Je sais, je peux commencer avec le moins dépensé montant et le travail de l'avant.

Peut quelqu'un m'indiquer le meilleur si vous l'avez.

Merci d'avance.

Pour résumer,
1. Trouver le total des frais et des dépenses par tête.
2. Trouver le montant de chaque redevable ou en circulation (-ve désigner en circulation).
3. Démarrer avec le moins de +ve montant. L'attribuent à l'-ve montant.
4. Répéter l'étape 3 jusqu'à ce que vous exécutez hors de la ve montant.
s. Passer à la prochaine plus grande +ve nombre. Continuez à répéter 3 & 4 jusqu'à ce qu'il y a +de cinq numéros.

Ou est-il une meilleure façon de faire? Je suis juste curieux. 🙂

source d'informationauteur Guru

algorithm

4

Vous avez décrit déjà. La somme de toutes les dépenses (1500 dans votre cas), diviser par le nombre de personnes partageant les frais (500). Pour chaque individu, de déduire les cotisations que la personne fait de la part individuelle (pour Une personne, de déduire de 400 à 500). Le résultat est sur le net que personne ne "doit" à la piscine centrale. Si le nombre est négatif pour toute personne, de la piscine centrale "doit" à la personne.

Parce que 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"?

Aussi, je ne sais pas ce que vous entendez par "démarrer avec le moins dépensé montant et le travail de l'avant."
10

La meilleure façon de revenir à l'état zéro (minimum de nombre de transactions) a été couvert dans cette question ici.
4

J'ai créé une application Android qui permet de résoudre ce problème. Vous pouvez entrer des dépenses pendant le voyage, il recommande même vous "qui doit payer la prochaine". À la fin, il calcule "qui devrait envoyer combien à qui". Mon algorithme calcule le minimum de nombre de transactions et vous pouvez configurer la transaction "tolérance", ce qui peut réduire les transactions encore plus loin (vous n'avez pas de soins sur 1 $de transactions) de l'Essayer, il est appelé à Régler:

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

Description de mon algorithme:

J'ai de base de l'algorithme qui résout le problème à n-1 opérations, mais il n'est pas optimale. Il 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. J'ai en quelque sorte 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'eux se retrouve avec un solde de zéro et est exclu de la suite des calculs. Avec cela, le nombre de transactions ne peut pas être pire que n-1. Il minimise aussi le montant de l'argent dans les transactions. Mais c'est pas optimal, car il ne détecte pas les sous-groupes qui peut régler en interne.

Trouver des sous-groupes qui peut régler en interne est dur. - Je le résoudre par la génération de toutes les combinaisons de membres et de vérifier si la somme des soldes dans le sous-groupe est égal à zéro. Je commence avec 2 paires, puis de 3 paires de ... (n-1)paires. Les implémentations de la combinaison de générateurs sont disponibles. Quand je trouve un sous-groupe, je calcule les transactions dans le sous-groupe à l'aide d'algorithme de base décrit ci-dessus. Pour chaque trouvés sous-groupe, une transaction est épargné.

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

Code Source:

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

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

L'idée (similaire à ce qui est demandé, mais avec un twist/à l'aide d'un peu de comptabilité concept) est d'utiliser la Piscine de Compte dans lequel, pour chaque projet de loi, les membres paient soit à la Piscine ou obtenir de la Piscine.
par exemple
dans l'image jointe ci-dessous, le Costco frais sont payés par M. P et les besoins de $93.76 de la Piscine et d'autres membres de payer $46.88 à la piscine.
1

J'ai récemment écrit un post de blog décrivant une approche pour résoudre le règlement des charges entre les membres d'un groupe où, potentiellement, tout le monde doit à tout le monde, tels que le nombre de versements nécessaires pour régler les dettes est le moins possible. Il utilise la programmation linéaire de la formulation. J'ai aussi de montrer un exemple à l'aide d'un minuscule paquet R qui implémente la solution.

Simple, comme vous le faites dans votre texte:

Renvoie les frais à payer par tout le monde dans le tableau d'origine.
Négatif valeurs: cette personne obtient quelques

Simplement la main tout ce que vous avez envers le prochain dans la ligne, puis l'abandonnent. Si vous l'obtenir, il suffit d'attendre le second tour. Quand c'est fait, inverser la totalité de la chose. 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;

Vous devez vous connecter pour publier un commentaire.