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.

[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

[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) }

[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 ?

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

[ekryyn]

?

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

non je veux dire qu'être le plus proche possible de L/2 n'impliquera pas l'optimalité de la solution : Ce but, être proche de L/2 pourrait parfois nous éloigner de l'optimalité

[pseudocode]

non je veux dire qu'être le plus proche possible de L/2 n'impliquera pas l'optimalité de la solution : Ce but, être proche de L/2 pourrait parfois nous éloigner de l'optimalité

heu... je peux avoir un exemple dans lequel la répartition optimale n'est pas la plus proche de S/2 dans chaque liste ?

[ekryyn]

heu... je peux avoir un exemple dans lequel la répartition optimale n'est pas la plus proche de S/2 dans chaque liste ?

J'ai effectivement du mal à trouver un contre-exemple. Ca doit être une bonne solution. Mais si on pouvait me prouver son optimalité autrement que par l'absence de contre exemple

Merci à tous pour vos contributions

[pseudocode]

J'ai effectivement du mal à trouver un contre-exemple. Ca doit être une bonne solution. Mais si on pouvait me prouver son optimalité autrement que par l'absence de contre exemple

Merci à tous pour vos contributions

ca doit se démontrer assez simplement.

Si on trouve une liste L1' qui est plus proche de S/2 que L1, alors forcément la liste L2' est elle aussi plus proche de S/2 que L2, puisque sum(L1)+sum(L2)=L.

Donc (L1', L2') est une meilleure solution au problème.

[ekryyn]

ca doit se démontrer assez simplement.

Si on trouve une liste L1' qui est plus proche de S/2 que L1, alors forcément la liste L2' est elle aussi plus proche de S/2 que L2, puisque sum(L1)+sum(L2)=L.

Donc (L1', L2') est une meilleure solution au problème.

Oui l'idée me paraît bonne.

Mais comment choisir les bons éléments pour que la somme se rapproche de S/2 de manière optimale ? On explore toutes les possibilités ?

[Zavonen]

Je croyais rếver, mais il me semble que je viens enfin de comprendre:

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,

Il fallait (peut-être) lire chaque élément de L possède UN pondérateur.
Ma proposition était fondée sur le fait que L était une liste de couples à coordonnées indépendantes. Mais dans cette hypothèse pourquoi répéter 2 fois dans l'exemple le couple (4,4) et ne pas mettre (4,8) à la place ?
Quand à votre S est-ce la somme brute des valeurs X ou bien la somme pondérée?
Il y a vraiment beaucoup de flou dans tout ça.

[ekryyn]

Je croyais rếver, mais il me semble que je viens enfin de comprendre:

Il fallait (peut-être) lire chaque élément de L possède UN pondérateur.
Ma proposition était fondée sur le fait que L était une liste de couples à coordonnées indépendantes. Mais dans cette hypothèse pourquoi répéter 2 fois dans l'exemple le couple (4,4) et ne pas mettre (4,8) à la place ?
Quand à votre S est-ce la somme brute des valeurs X ou bien la somme pondérée?
Il y a vraiment beaucoup de flou dans tout ça.

Les 2 valeurs sont bien indépendantes, je me suis certainement mal exprimé, mais dans un couple (X,Y), X et Y sont bel et bien indépendant, ils sont juste indissociables.

imaginons qu'il s'agit de lots en cailloux et en bout de bois
(4,4) signifie 4 cailloux et 4 bouts de bois

Le but de mon algo est de partager ces lots de façons à ce que tout le monde ait, autant que possible, autant de cailloux et de bouts de bois. Évidemment, ça ne tombera pas toujours juste, mais l'idéal serait qu'il y ait un minimum de différence entre chaque bénéficiaire, autant en termes de cailloux que de bouts de bois. Je suis désolé si j'exprime mal le problème, j'essaie d'être le plus clair possible.

EDIT: la tournure prête encore à confusion, décidément j'ai du mal à trouver la bonne. Ce qu'il me faut, c'est que L1 et L2 possède un nombre de bouts de bois le plus proche possible. Et pareil pour les cailloux. Sachant qu'ils sont distribués par lots.

[Zavonen]

Les 2 valeurs sont bien indépendantes, je me suis certainement mal exprimé, mais dans un couple (X,Y), X et Y sont bel et bien indépendant, ils sont juste indissociables.

Bon, alors S c'est quoi relativement à L ?
La somme des bouts de bois et des cailloux ?
Que représente alors S/2 ???

[ekryyn]

Bon, alors S c'est quoi relativement à L ?
La somme des bouts de bois et des cailloux ?
Que représente alors S/2 ???

S est la somme dans le cas où je n'ai que des éléments simples, par exemple que des cailloux. S était alors la somme de tous les cailloux. C'était histoire de découper le problème, plutôt que de prendre des éléments en couples, je pensais plus simple de réfléchir au même algo sur des éléments simples, par exemple, uniquement des cailloux.

Dans le cas des couples, on aurait deux sommes : S1 la somme des cailloux, et S2 la somme des bouts de bois dans L.

[Zavonen]

C'était histoire de découper le problème, plutôt que de prendre des éléments en couples, je pensais plus simple de réfléchir au même algo sur des éléments simples, par exemple, uniquement des cailloux.

Je ne pense pas que dans ce cas de figure précis, ce soit une bonne idée.

Dans le cas des couples, on aurait deux sommes : S1 la somme des cailloux, et S2 la somme des bouts de bois dans L.

Oui, c'est ce que j'appelle SX et SY dans ma proposition, qui dans ton exemple simple trouve exactement la solution que tu proposes.

[diablox0147]

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}

Je trouve ça pas mal.
mais peut-être un algo programation dynamique est plus adapté dans ce cas.