Discussion :

[barbouille]

Bonjour,

Je cherche à trouver en un minimum d'itérations la solution à ce problème :
- une balance à plateaux
- une série de poids pour le plateau de gauche (en grammes) :
- 7991/6765/2584/987/377/144/55/21/8/3/1
- une série de poids pour le plateau de droite (en grammes) :
- 10946/4181/1597/610/233/89/34/13/5/2
- le but du jeu est d'équilibre les plateaux avec le poids le plus lourd.

En le faisant bestialement, avec un algorithme qui calcule pour chaque plateau toutes les combinaisons de poids (2047 combinaisons), et faisant le rapprochement pour les 2 plateaux, j'arrive à un poids de 17572 par plateau ...

Seulement, mon algo est un peu long :
- 2047 combinaisons par côté,
- 2047*2047 confrontations pour trouver le plus grand poids commun

Sur les confrontations je peux facilement gagner en triant les combinaisons de poids et en comparant en partant de chaque côté par les plus lourdes.

Mais peut-on ne pas calculer toutes les ((2 puissance n) -1) combinaisons de poids par plateaux ?

Y'a-t-il une approche mathématique ou algorithmique du problème qui permettrait d'aller beaucoup plus vite ?

Merci

[Trap D]

J'ai l'impression que ça ressemble fort au problème du sac à dos.

[pseudocode]

si c'est une solution à ce probème en particulier, on peut sans doute optimiser (vue la règle utilisée pour la valeur des poids).

[Trap D]

Il me semble (je suis sûr) que la règle n'est pas vérifiée pour le nombre 7991, erreur de frappe où est-ce volontaire ?

[pseudocode]

Il me semble (je suis sûr) que la règle n'est pas vérifiée pour le nombre 7991, erreur de frappe où est-ce volontaire ?

ca doit être volontaire sinon il n'y aurait pas de solution pour parvenir à un équilibre.

[barbouille]

ca doit être volontaire sinon il n'y aurait pas de solution pour parvenir à un équilibre.

Oui effectivement il faut pouvoir équilibrer la balance.

si c'est une solution à ce probème en particulier, on peut sans doute optimiser (vue la règle utilisée pour la valeur des poids).

Et bah non, les valeurs données ne sont qu'un exemple. Je ne connais pas à l'avance la valeur des poids, ni leur nombre. Par contre il me faut dire si ça peut s'équilibrer, et si oui à quelle valeur, et ce le plus vite possible ...
J'ai fais un essai avec 13 poids de chaque côté, ça a pris 26s sur mon (vieux) PC pour tester toutes les combinaisons ...

J'ai l'impression que ça ressemble fort au problème du sac à dos.

Je me garde le lien dans un coin, j'irais jeter un coup d'oeil demain (trop sommeil là tout de suite maintenant )


En tout cas, pour vos réponses.

[Trap D]

ca doit être volontaire sinon il n'y aurait pas de solution pour parvenir à un équilibre.

Oui, j'y ai repensé par la suite ...
Je sortais d'une réunion parents-prof, j'ai une excuse M'sieur