|
Édition du: 13/02/2023 |
|
INDEX |
OPTIMISATION COMBINATOIRE |
||
|
Problème du sac à dos Knapsack problem (KP problem)
Problème
du sac à dos: problème d'optimisation du contenu d'un sac à dos. Un des 21 problèmes
de Richard Karp. Comment
obtenir un poids minimum et une valeur maximale avec des objets de poids et
de valeurs connus ? Le
problème est NP-complet,
ce qui signifie que l'on ne connaît pas de méthode générale pour construire
une solution optimale, à part l'examen systématique de toutes les solutions
envisageables. Autre
problème de ce genre: le problème
de la somme à payer avec un jeu de pièces données. Voir Optimisation
linéaire. |
||
|
|
Sommaire de cette page >>> Approche >>> Sac à dos – Procédé par ratio et tri >>> Sac à dos – Recherche systématique >>> Résolution rigoureuse >>> Problème de la somme de sous-ensembles >>> Anglais |
Débutants Glossaire |
|
Énigme Utilisez les
additions avec les nombres proposés pour atteindre un nombre imposé. Les nombres
proposés sont uniques et ils sont utilisés une seule fois. On impose
parfois un nombre maximum de termes dans l'addition. Commentaires L'exemple proposé
conduit à sept solutions ou, une seule en imposant un maximum de trois
termes. |
Problème E = {1, 2, 4, 5, 6, 7, 8} Faire N = 20 Solutions 20 = 5 + 7
+ 8 20 = 1 + 4 + 7 + 8 20= 1 + 5 + 6 + 8 20 = 2 + 4 + 6 + 8 20 = 2 + 5 + 6 + 7 20 = 1 + 2 + 4 + 5 + 8 20 = 1 + 2 + 4 + 6 + 7 |
|
|
Ce
qui est cherché Est-il possible
de remplir le sac-à-dos en maximisant la valeur des objets tout en respectant
la contrainte de poids ? Étant donné
plusieurs objets possédant chacun un
poids et une
valeur et étant
donné un poids
maximum pour le
sac, quels objets faut-il mettre
dans le sac
de manière à
maximiser la valeur
totale sans dépasser
le poids maximal autorisé pour
le sac ? |
Données
Poids maximum
autorisé 20 kg Solution Objets {1, 3, 4}
=> valeur 11 et poids 20. |
||||||||||||||||||||||||||||||||||
|
Méthode
approximative mais rapide Effectuer le
rapport valeur/poids et trier par ratio croissant. Dans l'exemple,
il se trouve que l'ordre est respecté. Choisir les
objets à fort ratio et les mettre dans
le sac à concurrence des 20 kg exigé. Avec cet exemple
simple, la méthode fonctionne. Ce n'est pas toujours le cas. Mais elle
produit un résultat rapide lorsqu'il y a une grande quantité d'objets. |
Ratio
et tri
Sélection Choix1: objet 4
avec 3kg Choix 2: objet 3
avec 3 + 7 = 10 kg dans le sac Choix 3: objet
2, poids (10 + 14) trop important Choix 4: objet 1
avec 10 + 10 = 20 kg Pour une valeur
de 5 + 4 + 2 = 11 euros. |
||||||||||||||||||||||||||||||||||
|
Deuxième
exemple Cet exemple
montre que la solution trouvée par la méthode ratio-tri est performante mais
pas optimale. Avec un objet en
moins, on gagne 1 kg pour une valeur augmentée de 1 euro. La solution
optimale a été trouvée à l'aide d'un programme
"bestial" qui examine toutes les possibilités. Procédé illusoire
avec un grand nombre d'éléments. |
Données
triées
Poids maximum :
40 Solution
selon la méthode Objet 7: 8;
Objet 5: 14; Objet 3: 21; Objet 4: 26; Objet: 6: 41; Non; Objet 2: 37 =>
[2, 3, 4, 5, 7] avec V = 36 et P = 37 Solution
optimale: [3, 5, 6, 7] avec
V = 37 et P = 36 |
||||||||||||||||||||||||||||||||||
|
Programme
Listing pour copier-coller restart; with(combinat); V := [2, 4, 8, 5, 8, 10,
11]; qV := nops(V); C := [10, 11, 7, 5, 6, 15, 8]; px := 40; vx := 0; Q :=
choose(qV): qQ := nops(Q): for j to qQ do QQ := Q[j]; qQQ := nops(QQ); val :=
add(V[QQ[i]], i = 1 .. qQQ); poids := add(C[QQ[i]], i = 1 .. qQQ); if poids
<= px and val > vx then sol := QQ, val, poids; vx := val end if end do;
sol; |
But du programme Maple Chercher la solution optimale du problème du sac
à dos par exploration systématique de toutes les solutions. Commentaires Réinitialisation et appel aux logiciels de
combinatoire. Données d'entrées V
pour valeurs et P pour poids. Poids max en
px. Valeur initiale (nulle) du sac en vx. En Q, toutes
les combinaisons (choose) sous le forme de
rangs (de pointeurs). Examen de chacune des combinaisons QQ. Calcul de la valeur et du poids pour cette
combinaison. Test si le poids est en dessous de la limite et
si la valeur, pour cette combinaison, dépasse toutes celles déjà trouvées. Si favorable, la variable sol mémorise la solution et la valeur du sac prend la
nouvelle valeur calculée. En fin de programme, édition de la solution
maximale en valeur pour un poids dans la limite fixée. Ici: ce sont les nombres en positions 3, 5, 6 et
7 qui réalisent la solution optimale avec une valeur de 37 (euros) pour 36
(kg). |
|
|
Exemple de solution
|
Valeurs croissantes et Poids décroissants. Poids max autorisé 40. La liste donne le rang des objets, ici confondu avec
la valeur des objets. Le sac pèse 36 kg pour 40 autorisé. |
|
|
|
Idem avec poids max de 30 kg. ici, 28 kg. Il est parfois possible d'approcher
davantage ou d'égaler le poids maximum, mais alors la valeur est plus faible. Cette solution donne bine la valeur maximale en
respectant la contrainte de poids. |
|
Voir Programmation – Index
|
La résolution
rigoureuse n'est possible que pour de petits ensembles de nombres et devient problématique
pour une grande quantité d'éléments. Ce problème est
inscrit dans la liste des 21 problèmes difficiles dits NP-complets de
Karp. Il existe des
méthodes heuristiques qui
approchent efficacement les solutions. Par exemple, une analyse de l'arbre des
possibilités avec élagage des branches non fructifères le plus rapidement
de manière à ne pas explorer toutes les combinaisons
possibles et ainsi optimiser le temps de calcul. La recherche de
ces solutions fait partie d'un domaine de l'informatique
appelé la programmation dynamique. |
|
Étant donné un ensemble E de n n entiers,
existe-t-il un sous-ensemble de E dont la somme des éléments est nulle ? Voisin du problème du sac à dos, ce problème est NP-complet,
difficile à résoudre par un algorithme. |
Exemples E= {-8, -3, -2,
4, 5} SE = {-3, -2, 5}
dont la somme est nulle E = {-6, -1, 2,
3, 8} SE nul
impossible |
|
|
The Knapsack Problem is a famous Dynamic Programming
Problem that falls in the optimization category. Given a set of items with specific weights and
assigned values, the goal is to maximize the value in a knapsack while
remaining within the weight constraint. |
Given two n-tuples of positive numbers {v1,
v2, … vn } et {w1, w2, … wn }
and N > 0, we wish to determine the subset T of {1, 2, …, n} that:
|
|
|
Retour |
|
|
Voir |
|
|
Sites |
|
|
Livre téléchargeable |
|
|
Cette page |
