Discussion :

[Programmeur13]

Bonjour,

je voudrais coder un algorithme de résolution du problème du sac à dos. Cependant, pour qu'il corresponde à mon sujet, il faudrait je pense aborder un problème du sac à dos multidimensionnel. Cependant, comme ce problème est beaucoup plus contraignant qu'un simple problème du sac à dos, j'aimerais savoir s'il y avait des alternatives. Je vous présente ma situation : je cherche à maximiser la valeur total sans dépasser une limite de poids mais aussi sans dépasser un nombre limite d'objets à mettre dans le sac. La contrainte supplémentaire est donc le nombre limité d'objets cependant, comme est peut-être "plus simple" que d'autres contraintes du problème du sac à dos multidimensionnel, n'existe-t-il pas des alternatives basés sur le problème du sac à dos avec des vérifications de non dépassement du seuil d'objet dans l'algorithme.

J'espère avoir été assez clair.

Merci à tous pour votre aide qui, je n'en doute pas, me sera très utile pour la suite.

[valentin03]

Comment pourrais-tu coder un algorithme quel qu'il soit si tu n'es pas capable de poser un test de dépassement ?

[Programmeur13]

Le problème n'est pas de coder le test de dépassement mais il suffit de coder l'algorithme de résolution du problème du sac à dos simple et d'y ajouter ce test ou faut-il obligatoirement utilisé un algorithme du sac à dos multidimensionnel ?

[dourouc05]

À ma connaissance, il n'existe pas de réduction du sac à doc multidimensionnel vers un sac à dos classique. Par contre, il existe des approches qui résolvent le problème multidimensionnel en n'utilisant que des sacs à dos classiques, comme https://homepages.laas.fr/elbaz/EJIE.pdf. Déjà, il faudrait savoir si tu cherches une solution exacte ou approchée au problème...

[Programmeur13]

C'est pour un projet d'étude, si les solutions exactes sont trop complexes à obtenir, des solutions approchées iront très bien. Sinon, tu penses que pour avoir ma contrainte de nombre d'objet maximum en plus de la contrainte du poids on est obligé de passer par un problème multidimensionnel. On ne peut pas juste rajouter des lignes de test dans le problème classique ?
Merci beaucoup

[dourouc05]

Si, tu peux juste ajouter des tests, mais tu n'as alors aucune garantie d'obtenir une bonne solution (ni même une solution, je crains...). Pour avoir une solution réalisable à coup sûr, je te proposerais plutôt une heuristique gloutonne : tu tentes de placer les objets en commençant par celui qui apporte le plus de valeur par rapport à son utilisation (donc celui qui maximise le ratio entre la valeur et la somme des poids dans chaque dimension) jusqu'à remplir ton sac.