Discussion :

[ben01n]

Je fais appel à vous car dans le cadre du développement d'une appli, je bloque sur un bout d'algo.
J'aurais besoin que mon soft puisse me calculer la répartition équitable dans un nombre défini de camions (qui peut changer à tout moment).

Par exemple :
j'ai 3 types de colis.
Le type de colis A pèse 50Kg.
Le type de colis B pèse 100Kg.
Le type de colis C pèse 150Kg.

Je dois transporter 5 colis A, 25 colis B et 10 colis C.
J'ai 3 camions à disposition.

L'objectif est de répartir au mieux le poids sur les 3 camions.

J'ai beau retourner le truc dans tout les sens, j'arrive pas à trouver le "truc".
Je suis sûr que c'est tout bête mais bon...

Quelqu'un a-t-il une idée ?

[pseudocode]

Bonjour,

Cela ressemble beaucoup a un "Subset Sum Problem" (dans ce cas précis, c'est meme du partitionnement). Il y a donc de grande chance que le problème soit NP et donc il n'y aura pas de "trucs" à part explorer l'arbre des solutions possibles.

[ben01n]

D'abord merci pour ta réponse rapide

C'est bien ce que je craignais....

Par contre, aurais-tu une idée sur la façon dont je pourrais procéder pour qu'une fois les solutions trouvés, le soft sélectionne la meilleur (plus équitable) ?

[pseudocode]

Par contre, aurais-tu une idée sur la façon dont je pourrais procéder pour qu'une fois les solutions trouvés, le soft sélectionne la meilleur (plus équitable) ?

Et bien prendre celle qui minimise la variance. Non ?

[ben01n]

J'ai pensé à une autre solution.
Peux-tu me dire ce que tu en pense :

Pour chaque colis du plus grand au plus petit, je prend le camion le moins chargé et lui attribu ce colis.

Pense-tu que cette répartition pourrait fonctionner ?
Je viens d'essayer avec quelques valeurs test et ça semble potable mais je ne sais pas si ça peut marcher de manière correcte tout le temps...

[pseudocode]

J'ai pensé à une autre solution.
Peux-tu me dire ce que tu en pense :

Pour chaque colis du plus grand au plus petit, je prend le camion le moins chargé et lui attribu ce colis.

Pense-tu que cette répartition pourrait fonctionner ?
Je viens d'essayer avec quelques valeurs test et ça semble potable mais je ne sais pas si ça peut marcher de manière correcte tout le temps...

C'est l'algorithme glouton. C'est une très bonne "première estimation" de la solution. On s'en sert généralement comme base de départ pour essayer d'optimiser la solution, par exemple en échangeant des colis entre les camions.

[ben01n]

Merci pour les renseignements.

J'ai adopté l'algo "glouton" pour le moment en attendant d'affiner la chose.