Le problème du sac à dos
Le sac à dos 0/1 et sa version fractionnaire : glouton par rapport valeur sur poids et ses limites, programmation dynamique sur la capacité, borne fractionnaire et séparation-évaluation.
- 23 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
Quelques cartes du deck
Problème du sac à dos : de quoi s'agit-il ?
Voir la réponse
Choisir parmi des objets, chacun de poids et de valeur donnés, ceux à emporter pour maximiser la valeur totale sans dépasser la capacité.
En version 0/1, chaque objet est pris entièrement ou laissé ; en version fractionnaire, on peut en prendre une part.
Capacité 50 ; objets (poids, valeur) : A (10, 60), B (20, 100), C (30, 120). Que rend le glouton par rapport valeur sur poids, et que vaut l'optimum 0/1 ?
- Glouton : 160 (A et B) ; optimum : 220 (B et C)
- Glouton : 220 (B et C) ; optimum : 220 (B et C), le glouton y arrive ici
- Glouton : 160 (A et B) ; optimum : 160, aucune autre combinaison ne fait mieux
- Glouton : 160 (A et B) ; optimum : 180 (A et C)
Voir la réponse
Glouton : 160 (A et B) ; optimum : 220 (B et C)
Rapports : A 6, B 5, C 4. Le glouton prend A et B (poids 30, valeur 160) ; C pèse 30 et ne rentre plus (reste 20). Mais B + C pèse exactement 50, ce qui est permis, pour 220 : mieux que A + C (180).
Pour le sac à dos 0/1 à n objets et de capacité W, la table de programmation dynamique a une ligne par … et une colonne par … de 0 à W, d'où un temps en O(nW).
Voir la réponse
Pour le sac à dos 0/1 à n objets et de capacité W, la table de programmation dynamique a une ligne par objet et une colonne par capacité de 0 à W, d'où un temps en O(nW).
Une case par couple (nombre d'objets considérés, capacité), plus une ligne 0 sans objet et une colonne de capacité 0. Chaque case se calcule en temps constant à partir de la ligne précédente.
Algorithme glouton : de quoi s'agit-il ?
Voir la réponse
Méthode qui construit une solution par une suite de choix, chacun pris au mieux sur le moment et jamais remis en cause.
Pour le sac à dos : trier par rapport valeur sur poids décroissant, puis prendre tant que ça rentre. Optimal en version fractionnaire, pas en 0/1.