Problème du sac à dos

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

Nombres

Glossaire

Nombres

Approche

haut

É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

Sac à dos – Procédé par ratio et tri

haut

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

Objets	1	2	3	4
Valeur	2	4	4	5
Poids	10	14	7	3

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

Objets	1	2	3	4
Valeur	2	4	4	5
Poids	10	14	7	3
V / P	0,2	0,3	0,6	1,7

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

Objets	1	2	6	4	3	5	7
Valeur	2	4	10	5	8	8	11
Poids	10	11	15	5	7	6	8
V / P	0,20	0,36	0,67	1,00	1,14	1,33	1,38

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

Sac à dos – Recherche systématique

haut

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

Résolution rigoureuse

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.

Voir Optimisation linéaire

Problème de la somme de sous-ensembles

haut

É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

Voir Problèmes des MCNuggets

English Corner

haut

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 {v₁, v₂, … v_n} et {w₁, w₂, … w_n} and N > 0, we wish to determine the subset T of {1, 2, …, n} that:

Haut de page

Retour	Voir Haut de page
Voir	Algorithme des fourmis Le défi du métro parisien Les trajets – Compter les itinéraires d'un point à un autre Logique formelle Marche de l'ivrogne Nombres Mc Nugget Parcours des abeilles Parcours du taxi Problème du pont de Königsberg
Sites	Problème du sac à dos – Wikipédia Le problème du sac à dos
Livre téléchargeable	Knapsack Problems – Algorithms and Computer Implementation – Silvano Martello and Palo Toth – 1990 – pdf 306 pages – Niveau supérieur
Cette page	http://diconombre.fr/LogForm/Sacados.htm