Problème du sac à dos

Bonjour,

J'ai deux sacs à dos de n emplacements.
Je dois placer n*2 objets de masse différentes.
Il faut équilibrer un maximum pour que la différence soit minimale et pour éviter de faire basculer l'âne sur lequel je vais mettre les sacs.

J'ai tout de suite pensé au problème du sac à dos et en cherchant j'ai pensé que la solution du problème Sac à dos multiple de même contenance aussi appellé MKP-I mais je n'ai pas trouvé de solution pour résoudre cet exercice.

Merci de me donner des pistes, des solutions car après de longues recherches je n'ai toujours rien trouvé.

Merci d'avance et bonne prog,
Joyeuses fêtes de fin d'année !
@++

Victor

c'est cool prologin.

Bonjour,

Personne pour donner une piste une une documentation sur le sac à dos multiple de même contenance ?

Merci et bonne prog,
@++

Victor

salut

demander sur CodeS-SourceS une solution pour un exercice de prologin, je trouve ca assez gonfle...

je te donnerais la solution le 5 janvier, quand les soumissions du QCM seront passees

Bonjour,

Je ne cherche pas un exo de prologin mais des pistes pour un exos que j'ai à faire pour mon prof d'algo.

Merci et bonne prog,
@++

Victor [ Lien ]

http://www.prologin.org/?q=contest/qcm/2009/view

tout en bas, c'est exactement le meme exercice

Bonjour,

Ah ouai en différent mais c'est le même.

Dans ce cas donne juste des pistes, je comprends qu'il ne faut pas donner la solution avant la fin du QCM.

Merci et bonne prog,
@++

Victor [ Lien ]

c'est un probleme np complet qui a une solution dynamique en O( n * somme des valeurs )

le principe etant de placer n elements parmi 2n elements, de facon a ce que la somme de leurs poids ne depasse pas (somme des valeurs) /2

Bonjour,

Je m'étais dis ça aussi.
Du coups j'avais rempli les sacs en classant les poids en décroissance et en mettant dans un sac en déficit de poids le poids suivant.
Mais cette méthode ne prend pas en compte la compensation pour certain cas.
Après j'avais fait l'algo glouton pour remplir un sac (de capacité somme des valeurs / 2) et mis le reste ainsi que les plus petits excédents du premier sac dans le second mais ça ne marchait toujours pas.

Et puis j'ai pas de livre d'algo parlant des problème np complet.
Les docs que j'ai trouvé sont en anglais et je sais même pas si elles correspondent à ce qui me faut.
Les maths algorithmique en anglais c'est pas facile à lire.

Merci pour tes pistes constructives mais ce que tu m'as dit je l'avais trouvé.
N'aurais-tu pas d'autres pistes ?

Merci et bonne prog,
@++

Victor [ Lien ]

Bonjour,

J'ai oublié de dire que j'avais fait du récursif en évitant de prendre toutes les possibilités mais en prenant seulement les possibilités possibles un peu à la manière des algo génétique mais sans stocker ça en mémoire mais par exemple pour 40 objets on a 2* 68923264410 possibilités (j'en élimine la moitié car si on met par exemple 2+3 dans le sac A et 4+5 dans le sac B ça revient à mettre 4+5 dans le sac A et 2+3 dans le B).

Merci et bonne prog,
@++

Victor [ Lien ]