Accueil

Orientation générale

Barre de recherche

DicoNombre

DicoMot Math

DicoCulture

Atlas des maths

Rubriques

Index alphabétique

Nouveautés

Actualités

Références

Édition du: 02/06/2021

M'écrire

Brèves de Maths

 

INDEX

 

Dénombrement

Graphes

Algorithmes

Problèmes modernes

Jeux et énigmes

OPTIMISATION COMBINATOIRE

Pesées

Sac à dos

Faire n sous contrainte

Algorithme LLL

Voyageur de commerce

 

 

Problème du sac à dos

Knapsck 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.

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

>>> 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 ProgrammationIndex

 

 

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

 

 

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 {v1, v2, … vn } et {w1, w2, … wn } 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

*      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://villemin.gerard.free.fr/LogForm/Sacados.htm