Contenus

Problème du sac à dos

Le problème du sac à dos est l’un des 21 problèmes NP-complets de Richard Karp, exposés dans son article de 1972.

Énoncé

Le problème du sac à dos modélise une situation analogue au remplissage d’un sac à dos, ne pouvant supporter plus d’un certain poids, avec tout ou partie d’un ensemble donné d’objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum.

La forme la plus commune est le problème de sac à dos 0-1 (0-1 KP), restreignant le nombre de copies x_i de chaque objet i à un exemplaire au maximum. Soient un ensemble de n objet, muni d’un poids w_i et d’une utilité v_i, et la capacité du sac à dos W, le problème s’écrit comme suit:

maximize ∑_i=1ⁿ v_i*x_i

subject to ∑_i=1ⁿ v_i*x_i ≤ W and x_i ∈ {0,1}.

Le problème du sac à dos limité (bounded knapsack problem BKP) retire la restriction de limitation de l’objet par une limitation bornée par un entier c_i:

maximize ∑_i=1ⁿ v_i*x_i

subject to ∑_i=1ⁿ v_i*x_i ≤ W and x_i ∈ {0, … , c_i}.

Le problème du sac à dos illimité (unbounded knapsack problem UKP) ne place aucune restriction sur le nombres de copies de chaque objet.

maximize ∑_i=1ⁿ v_i*x_i

subject to ∑_i=1ⁿ v_i*x_i ≤ W and 0≤x_i .

Il existe bien d’autres variantes du problème du sac à dos qui sont décrite dans une autre page. Merci de vous référer à la Réduction polynomiale.

Méthodes de résolution

Algorithme glouton

L’idée est d’ajouter en priorité les objets les plus efficaces, jusqu’à saturation du sac :

 Trier les objets par ordre décroissant d'efficacité
w_conso := 0

pour i de 1 à n
  si w[i] + w_conso ≤ W alors
    x[i] := 1
    w_conso := w_conso + w[i]
  sinon
    x[i] := 0
  fin si
fin pour

Programmation dynamique

Le problème du sac à dos possède la propriété de sous-structure optimale, i.e. que l’on peut construire la solution optimale du problème à k variables à partir du problème à k – 1 variables.

Soit F_k(E) le meilleur cout pour remplir un sac de taille E avec les k
premiers objets. La récurrence montre queF_k(E) = max{F_k−1(E), F_k−1(E − w_k)+v_k},

en effet l’ajout d’un nouvel objet augmente ou non le meilleur cout. Dans le cas où le nouvel objet n’est pas rajouté au sac, F_k(E) est égale à F_k−1(E). Dans le cas où le nouvel objet offre une meilleure utilité, i.e. dans le cas où l’objet n’est pas présent mais que le sac (sans l’objet) possède la place suffisante pour accueillir le nouvel élément, et qu’il soit optimal (soit la formule F_k−1(E − w_k)), alors F_k(E) est égale à F_k−1(E − w_k) + v_k, v_k étant l’utilité du nouvel objet rajouté dans le sac décrit précédemment.

Nous donc cherchons à calculer F_n(W), avec n le nombre total d’objet et W la taille maximale du sac à dos étudié.

pour c de 0 à W faire
  T[0,c] := 0
fin pour

pour i de 1 à n faire
  pour c de 0 à W faire
    si c>=w[i] alors
      T[i,c] := max(T[i-1,c], T[i-1, c-w[i]] + p[i])
    sinon
      T[i,c] := T[i-1,c]
    fin si
  fin pour
fin pour

Nous disposons des éléments suivants : C = 8, et cinq objets décrits dans
le tableau ci-dessous

i	1	2	3	4	5
p_i	3	4	5	4	2
u_i	15	18	20	12	6

Nous obtenons le tableau de résultat du sac à dos suivant :

E\|i	1	2	3	4	5
0	0	0	0	0	0
1	0	0	0	0	0
2	6	6	6	6	6
3	15	6	6	6	6
4	15	18	12	12	6
5	21	20	20	12	6
6	24	24	20	18	6
7	33	26	26	18	6
8	35	30	26	18	6

La solution optimale de 25 est obtenue avec les éléments 1 et 3 d’après le second
algorithme du sac à dos :

k	1	2	3	4	5
E	8	5	5	0	0
x[k]	1	0	1	0	0

conso = conso_1 + conso_3 = 8.