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 xi de chaque objet i à un exemplaire au maximum. Soient un ensemble de n objet, muni d’un poids wi et d’une utilité vi, et la capacité du sac à dos W, le problème s’écrit comme suit:

maximize ∑i=1n vi*xi
subject to ∑i=1n vi*xi ≤ W and xi ∈ {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 ci:

maximize ∑i=1n vi*xi
subject to ∑i=1n vi*xi ≤ W and xi ∈ {0, … , ci}.

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

maximize ∑i=1n vi*xi
subject to ∑i=1n vi*xi ≤ W and 0≤xi .

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 Fk(E) le meilleur cout pour remplir un sac de taille E avec les k
premiers objets. La récurrence montre queFk(E) = max{Fk−1(E), Fk−1(E − wk)+vk},

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, Fk(E) est égale à Fk−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 Fk−1(E − wk)), alors Fk(E) est égale à Fk−1(E − wk) + vk, vk étant l’utilité du nouvel objet rajouté dans le sac décrit précédemment. Nous donc cherchons à calculer Fn(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.

Publicités