Knapsack problem

The knapsack problem is one of 21 NP-complete problems of Richard Karp, set out in his 1972 paper.

Definition

The knapsack problem models a situation analogous to filling a backpack, could not bear more than a certain weight, with all or part of a given set of objects each having a weight value. The objects put in the backpack must maximize the total value, without exceeding the maximum weight.

The most common form is the 0-1 knapsack problem(0-1 KP), restricting the number of copies of each object xi to one copy. Are a set of n object, provided with a weight wi and a utility vi, and the capacity of the backpack W, the problem is written as follows:

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

The problem of the bounded knapsack problem (BKP) rewrites the restriction of the object  by an integer ci:

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

The unbounded knapsack problem (UKP) does not place restrictions on the number of copies of each object.

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

Methods

Greedy algorithm

The idea is to add in priority the most effective objects, until saturation of the knapsack:

Sort objects in descending order of efficiency
w_conso := 0

For i from 1 to n
  If w[i] + w_conso ≤ W then
    x[i] := 1
    w_conso := w_conso + w[i]
  Else
    x[i] := 0
  End if
End

Dynamic programming

The knapsack problem has the property of optimal substructure, i.e. that one can construct the optimal solution of the problem to k variables from the problem to k-1 variables.

Soit  le meilleur cout pour remplir un sac de taille E avec les k
premiers objets. La récurrence montre que

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,  est égale à . 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 ), alors  est égale à  étant l’utilité du nouvel objet rajouté dans le sac décrit précédemment. Nous donc cherchons à calculer , avec n le nombre total d’objet et W la taille maximale du sac à dos étudié.

Let Fk(E) be the best cost to fill a size E bag with k first objects. The recurrence shows that Fk(E) = max{Fk−1(E), Fk−1(E − wk)+vk}, indeed the addition of a new object increases or not the best cost. In the case where the new object is not added to the bag, Fk(E) is equal to Fk−1(E). In the case where the new object offers a better utility, ie in the case where the object is not present but the bag (without the object) has sufficient space to accommodate the new element, and that it is optimal (ie the formula Fk−1(E − wk)), then Fk(E) is equal to Fk−1(E − wk) + vk, vk being the utility of the new object added in the bag described previously. We therefore try to calculate Fn(W), where n is the total number of objects and W is the maximum size of the backpack studied.

For c from 0 to W
  T[0,c] := 0
End for

For i from 1 to n
  For c from 0 to W
    If c>=w[i] then
      T[i,c] := max(T[i-1,c], T[i-1, c-w[i]] + p[i])
    Else
      T[i,c] := T[i-1,c]
    End if
  End for
ENd

We have the following elements: C = 8, and five objects described in
the table below

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

We get the result table of the following knapsack:

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

The optimal solution of 25 is obtained with the elements 1 and 3 according to the second algorithm:

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