Algorithme qui est une combinaison du problème du sac à dos continu et du problème d'empaquetage de la corbeille à taille variable

Question

J'essaie de résoudre un problème (en PHP, mais le langage de programmation n'a pas d'importance). Je vais avoir un n nombre de personnes qui ont payé l'argent, et j'ai un m nombre de personnes qui vont payer le même montant que la somme de ce que le n nombre de personnes ont payé . Je veux calculer l'itinéraire le plus court des transferts d'argent entre ces personnes. Il est possible de fractionner les paiements et de payer à différentes personnes. L'idéal est qu'une personne ne fasse qu'une ou deux transactions. Quelqu'un peut-il me diriger dans la bonne direction ou m'aider avec cela?

Un exemple: personne A a honoraires de 100 $

personne B a payé 200 $

personne C a payé 50 $

personne D paiera 24 $

personne E paiera 175

$

personne F paiera 151 $

Une solution possible est

personne E paie 100 $ à la personne A,

personne E paie 75 $ à la personne B,

personne F paie 125 $ à la personne B,

la personne F paie 26 $ par personne C

personne D paie 24 $ par personne C

Answer 1

En théorie, cela pourrait être considéré comme un problème d'optimisation:

Fondamentalement, nous allons établir un ensemble de contraintes qui énumèrent la structure de votre problème, ensemencer les valeurs initiales, et nous assurer que nous allouons tout l'argent comme vous avez indiqué.

contraintes de condition initiale:

A_paid = 100 
B_paid = 200 
C_paid = 50 
D_out = 24 
E_out = 175 
F_out = 151 

Montant versé ne peut excéder le montant disponible: (nous définissons D_to_A comme une variable dont le montant payé par personne D à personne A)

D_out >= D_to_A + D_to_B + D_to_C 
E_out >= E_to_A + E_to_B + E_to_C 
F_out >= F_to_A + F_to_B + F_to_C 

Montant payé à chaque individu doit être égal à ce qu'ils ont déjà payé:

A_paid = D_to_A + E_to_A + F_to_A 
B_paid = D_to_B + E_to_B + F_to_B 
C_paid = D_to_C + E_to_C + F_to_C 

Si nous devions arrêter maintenant et résoudre ce problème en tant que programme linéaire, nous trouverions une solution couvrant l'ensemble de l'espace variable, mais vous cherchez à minimiser le nombre de paiements réels. Nous pouvons le faire en minimisant toutes les variables X_to_Y de concert avec les contraintes ci-dessus.

min: D_to_A + D_to_B + D_to_C + ... 

Vous pouvez utiliser votre technique préférée d'optimisation pour résoudre le problème, il y a beaucoup de solveurs de programmes linéaires disponibles, j'aime lpsolve. Bien que cela résout l'exemple spécifique que vous avez décrit, il est facile de voir comment il peut être étendu à des problèmes plus importants en ajoutant plus de variables ... mais le problème augmente considérablement en complexité lorsque vous ajoutez des personnes. Si je me souviens bien, le problème du sac à dos est NP ou NP-difficile, donc ce n'est pas inattendu.