Discussion :

[ekryyn]

Bonjour à tous,

Je dispose d'une liste d'éléments valués, et j'aimerais être capable de répartir ces éléments sur N listes de la manière la plus équitable possible.

Par exemple, je dispose d'un ensemble d'éléments dont les valeurs sont les suivantes :

L = { 2, 4, 3, 5, 8, 2 }

Je cherche à écrire un algorithme qui distribue ces valeurs sur L1 et L2 de manière à ce que la différence entre la somme des éléments de L1 et la somme des éléments de L2 soit la plus petite possible.

Cet algorithme me servira pour une liste d'éléments un peu plus complexe. En effet, mes éléments ont 2 valeurs qui les pondèrent, un élément est noté sous la forme (X,Y) où X et Y sont les 2 valeurs qui le caractérisent :

L = { (2,5) , (4,10) , (3,12), (5,7) }

Et dans ce cas plus complexe, je souhaite que mon algorithme répartisse les éléments sur L1 et L2 de manière à limiter la différence de la somme des X ET limiter la différence de la somme des Y entre L1 et L2.

Avez-vous une idée de la façon dont je dois m'y prendre ?

[Zavonen]

Y-a-t-il une contrainte sur la taille des listes L1 et L2 ?

[ekryyn]

Non il n'y a pas de contrainte sur la taille de L1 et L2.

si la solution optimale attribue 9 éléments à L1 et 1 seul à L2, ça ne pose pas de soucis. Tout ce qui importe, c'est que la somme des éléments de L1 soit la plus proche possible de la somme des éléments de L2

[Zavonen]

Pour toute liste L de couples on pose SX(L) = la somme des premiers éléments et SY(L), la somme des seconds éléments.
Pour tout couple de telles listes, tu poses D(L1,L2)=|SX(L1)-SX(L2)|+|SY(L1)-SY(L2)|
Une idée d'algo 'bourrin'.
Au départ L1 et L2 sont vides
Tu prends le premier couple de L et tu le mets dans L1, le second tu le mets dans L2.
Après tu examines les éléments de L un à un et tu simules de les mettre soit dans L1 soit dans L2 et tu calcules à chaque fois le D(L1,L2). Tu prends l'élément de L qui minimalise et tu le places soit dans L1 soit dans L2 selon le cas. Puis tu recommences jusqu'à épuisement de tous les éléments de L.
Si L est de taille n cet algo est en n^2, donc pas génial du point de vue de l'efficacité.
Si tu veux un algo en n, tu prends les éléments de L dans l'ordre où il se présentent et tu les mets soit dans L1 soit dans L2 en minimisant à chaque fois.
En outre je ne suis pas sûr du tout que ces algos conduisent à des solutions optimales.
Mais enfin, c'est une proposition.

[ekryyn]

Pour toute liste L de couples on pose SX(L) = la somme des premiers éléments et SY(L), la somme des seconds éléments.
Pour tout couple de telles listes, tu poses D(L1,L2)=|SX(L1)-SX(L2)|+|SY(L1)-SY(L2)|
Une idée d'algo 'bourrin'.
Au départ L1 et L2 sont vides
Tu prends le premier couple de L et tu le mets dans L1, le second tu le mets dans L2.
Après tu examines les éléments de L un à un et tu simules de les mettre soit dans L1 soit dans L2 et tu calcules à chaque fois le D(L1,L2). Tu prends l'élément de L qui minimalise et tu le places soit dans L1 soit dans L2 selon le cas. Puis tu recommences jusqu'à épuisement de tous les éléments de L.
Si L est de taille n cet algo est en n^2, donc pas génial du point de vue de l'efficacité.
Si tu veux un algo en n, tu prends les éléments de L dans l'ordre où il se présentent et tu les mets soit dans L1 soit dans L2 en minimisant à chaque fois.
En outre je ne suis pas sûr du tout que ces algos conduisent à des solutions optimales.
Mais enfin, c'est une proposition.

Prenons les couples suivants :
L ={ (9,9) , (4,4) , (4,4) }

J'ai dû mal à voir comment appliquer ta méthode sur un truc pareil. Peux tu me l'expliquer avec cet exemple ?


Edit : la solultion optimale pour cet ensemble de couples semble être :
L1 = { (9,9) }
L2 = { (4,4) , (4,4) }

[ekryyn]

J'ai eu une idée qui me paraissait être une bonne piste. Cependant j'aimerais votre avis :

Prenons un ensemble d'éléments simples :

L = { 9, 4, 2, 2 }
L1 = {} ; L2 = {}

L'idée est de commencer par le plus "coûteux" présent dans L, l'élément de valeur 9

L = { 4, 2, 2}
L1 = {9} ; L2 = {}
On le place en L1 car il faut bien le mettre dans une liste

De même, on place l'élément de valeur 4 car il est le plus coûteux restant :
L1 = {9} ; L2 = {4}
là par contre, on le met en L2 car la somme des éléments de L2 se rapproche de celle de L1 si on y met ce 4.

L = { 2, 2}
L1 = {9} ; L2 = {4}

Il nous reste deux 2, on prend le premier, et on regarde où il minimiserait la différence des sommes : en L2 évidemment

L = { 2}
L1 = {9} ; L2 = {4,2,}

pareil pour le dernier 2

L1 = {9} ; L2 = {4, 2, 2}

[pseudocode]

Tu peux calculer la somme 'S' des éléments de L, puis faire une exploration pour chercher la sous liste dont la somme se rapproche le plus de S/2

[ekryyn]

Tu peux calculer la somme 'S' des éléments de L, puis faire une exploration pour chercher la sous liste dont la somme se rapproche le plus de S/2

L'idée me paraît séduisante mais il faut l'affiner : trouver une somme proche de S/2 n'implique pas un écart moindre entre les deux sommes... Il faudra parfois s'éloigner du S/2 pour minimiser la différence des sommes

[pseudocode]

L'idée me paraît séduisante mais il faut l'affiner : trouver une somme proche de S/2 n'implique pas un écart moindre entre les deux sommes... Il faudra parfois s'éloigner du S/2 pour minimiser la différence des sommes

?

Tu veux dire que tu peux avoir certains éléments de L qui ne seront ni dans L1, ni dans L2 ?