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.

Salut, je pense que la programmation dynamique résout ton cas, il faut juste considérer le nombre d'objet en plus du poids dans ton sac.

En fait il s'agit d'un projet en tant qu'étudiant et j'aurais voulu apporter plusieurs approches à la résolution. Pensez-vous qu'on peut aussi adapter l'algorithme glouton ou l'approche génétique par exemple ?

Yes c'est un classique en tant qu'étudiant (je l'ai fais cette année). Pour ce qui est des autres approches, tu peux implanter un algorithme glouton mais il sera moins performant que la programmation dynamique. Je ne connais pas bien l'approche génétique, et je vais éviter de dire des âneries dessus ^^.

Pour l'algorithme glouton, il suffit de mettre une condition sur le nombre limite d'objet en plus de celle sur la limite de poids dans la boucle ? On ne perd pas de potentielles meilleures solutions en faisant cela ?

Le but d'un algorithme glouton est de définir une ligne à suivre et de la suivre jusqu'au bout. A toi donc de créer le facteur qui va bien. A ta place, je prendrai tous les objets qui ont le meilleur rapport valeur/poids et tu mets bel et bien une condition pour le nombre d'objets.
Après, un algorithme glouton est là pour obtenir une solution qui est potentiellement la meilleure, mais on n'a pas de garantie là dessus, par contre c'est un algorithme qui s'exécute en temps raisonnable.

Pour être sûr, un algorithme glouton peut gérer de grande quantité d'objet rapidement mais donne un résultat bon mais pas forcément optimal. Un algorithme génétique donne un meilleur résultat mais en plus de temps et peut également supporter un grand nombre d'objet. Et l'algorithme dynamique est le plus optimal mais est plus long et gère de plus petite quantité d'objet. Est-ce bien cela ?

Merci

L'algorithme glouton c'est plus ou moins ça, tu prends une ligne conductrice (dans l'exemple c'est le rapport valeurs/poids) et tu la suis jusqu'au bout.
L'algorithme génétique je ne connais pas vraiment le sujet donc je ne peux pas me prononcer.

On parle de programmation dynamique et non d'algorithme dynamique, cela consiste à découper le problème en sous problème, stocker les résultats intermédiaires et ensuite tu te sers des solutions pour résoudre le problème initial.

Quelle est la différence entre la programmation dynamique et la récursivité ?

Et je ne sais pas si tu pourras me répondre mais avec un ordinateur "classique" quelle est la taille maximale du problème qu'on peut traiter en temps raisonnable ?

Merci pour ton aide

Récursivité : fonction qui s'appelle elle-même

Programmation dynamique : dans le problème du sac à dos tu vas d'abord chercher à déterminer la meilleure solution pour un sac avec un poids de 1, de 2 etc jusqu'à ton poids max.

Qu'est ce que tu entends par taille?

J'entends le nombre maximal d'objet disponibles à mettre dans le sac.

Alors là j'en ai aucune idée^^

Mais du coup tu penses que pour ma limitation de nombre d'objets, on peut conserver les solutions pour le problème du sac à dos simple en rajoutant au bon endroit cette contrainte sans perdre en qualité des solutions ? On n'a pas besoin d'algorithmes plus poussés comme pour le problème multi-dimensionnel ou multi-objectif ?

Une autre question que je me posais, une variante où on cherche à optimiser la valeur d'un chargement sur l'ensemble d'un trajet comportant des escales, où les objets ont un point d'arrêt qui peut être différent de l'arrivée finale est-elle envisageable ?

Par exemple, un trajet comporte 3 escales et certains objets qu'on prend au départ doivent être déposés sur l'une de ces escales et on en prend d'autres pour les remplacer. On veut que la valeur totale transportée sur l'ensemble du trajet soit maximale.

J'ai du mal à voir si c'est un problème concevable pour un étudiant ou si le problème est trop poussé.

Le problème du sac à dos est déjà en soit un problème qui a été résolu au bout de plusieurs années de recherches. Je me suis pas posé la question d'une version multidimensionnelle, je pense qu'un algorithme glouton est simple à mettre en place, la programmation dynamique sans doute un peu moins.
La série de problème dont tu parles fait partie de la famille des problèmes NP, donc trouver une solution qui est exacte tout le temps est impossible en temps raisonnable(du moins aujourd'hui), on peut seulement approcher des résultats.

Beaucoup d'équipes de chercheurs bossent sur ce genre de questions dont les solutions auraient des impacts considérables sur beaucoup de choses (notamment le domaine de la logistique pour tout ce qui est problème de voyageur de commerce etc).

Cependant, cela ne doit pas t'empêcher de t'intéresser à ces questions, tu y apprendras énormément.