dans le sac
Poids
Meilleur possible

    Objets

      Plus sur le problème du sac à dos

      Problème du sac à dos

      Vous ne pouvez porter qu'un certain poids, et chaque objet a un poids et une valeur. Quels objets prendre pour emporter le plus de valeur ? Essayer toutes les combinaisons double le travail à chaque objet. Un tableau avec une ligne par objet et une colonne par capacité trouve le meilleur sac, une case après l'autre. Touchez un objet pour le mettre dans le sac, et touchez-le à nouveau (dans le sac ou sur l'étagère) pour le retirer. Le sac se remplit selon le poids, et les vignettes comparent les dollars que vous avez mis dans le sac au meilleur résultat possible. Appuyez sur Meilleur remplissage pour voir le meilleur sac. Dans le panneau, modifiez les kilos et les dollars des objets, ajoutez ou supprimez des objets et réglez la capacité du sac. La vue Tableau montre comment la programmation dynamique trouve le meilleur sac : appuyez sur Lecture pour voir le tableau se remplir, ou sur Étape et Retour pour aller d'une étape à la fois, et faites glisser le curseur des étapes pour aller n'importe où. Chaque ligne ajoute un objet, chaque colonne est une capacité en kilos, et chaque case contient le maximum de dollars qui tient dans le sac. Quand le tableau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause la lecture, et les touches Début et Fin vont au début et à la fin.

      Comment ça marche

      1. Touchez les caisses pour les mettre dans le sac, et regardez-le se remplir selon le poids en kilos.
      2. Essayez d'atteindre la meilleure valeur possible en dollars, ou appuyez sur Meilleur remplissage pour voir le meilleur sac.
      3. Ouvrez la vue Tableau et appuyez sur Lecture pour voir chaque case choisir entre prendre et laisser un objet.

      Comment fonctionne le tableau

      Chaque ligne ajoute un objet et chaque colonne est une capacité, de 0 jusqu'à celle du sac. Une case contient la plus grande valeur qui tient dans cette capacité avec les objets jusqu'à sa ligne. Sans le nouvel objet, c'est la case du dessus. Avec lui, s'il tient, c'est la valeur de l'objet plus la meilleure valeur pour le poids restant, qui se trouve dans la ligne du dessus, décalée vers la gauche du poids de l'objet. La case garde la plus grande des deux. La première ligne, sans objet, ne contient que des zéros.

      Retrouver les objets

      La case en bas à droite est la meilleure valeur. Pour trouver les objets, partez de là et comparez-la avec la case du dessus : si elle est égale, le dernier objet n'était pas nécessaire ; si elle est plus grande, l'objet est dans le sac, donc soustrayez son poids et allez à cette colonne. Montez d'une ligne à chaque fois jusqu'à la première ligne. L'application montre cette remontée en orange et liste les objets mis dans le sac sous le tableau.

      Questions fréquemment posées

      Que signifie 0/1 dans le problème du sac à dos 0/1 ?

      Chaque objet est pris une fois ou pas du tout, jamais en partie et jamais deux fois. Si l'on pouvait couper les objets, comme des grains de riz, prendre d'abord la meilleure valeur par poids serait optimal ; c'est le problème du sac à dos fractionnaire.

      Pourquoi ne pas prendre d'abord la meilleure valeur par poids ?

      Parce que des objets entiers peuvent laisser des trous. Avec une capacité de 7 et des objets de poids 1, 3, 4 et 5 valant 1, 4, 5 et 7, la meilleure valeur par poids est celle de l'objet de poids 5, qui ne laisse de place que pour l'objet de poids 1, pour un total de 8. Les objets de poids 3 et 4 valent ensemble 9.

      L'algorithme du sac à dos est-il rapide ?

      Le tableau a (nombre d'objets + 1) fois (capacité + 1) cases, chacune remplie en une étape. C'est rapide pour de petites capacités, mais une capacité peut être un nombre énorme, donc le problème est NP-difficile en général ; la méthode du tableau est dite pseudo-polynomiale.

      Peut-on mettre le même objet deux fois ?

      Pas ici. Dans le problème du sac à dos non borné, chaque objet peut être pris autant de fois que l'on veut ; le tableau lit alors la case à gauche dans la même ligne au lieu de la ligne du dessus, comme dans l'application du rendu de monnaie.

      Des données sont-elles envoyées quelque part ?

      Non. Tout est calculé dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

      Prêt à l'essayer ?

      Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

      Aller à l'éditeur