Contenus

Toggle## Backpack problem

The backpack problem is one of Richard Karp's 21 NP-Complete Problems, outlined in his 1972 article.

# States

The most common form is the 0-1 (0-1 KP) backpack problem, restricting the number of copies x_{i} of each object i to a maximum of one. Let be a set of n object, endowed with a weight w_{i} and of utility v_{i}, and the capacity of the backpack W, the problem is written as follows:

- maximize ∑
_{i = 1}^{not}v_{i}* x_{i} - subject to ∑
_{i = 1}^{not}v_{i}* x_{i}≤ W and x_{i}∈ {0.1}.

The bounded knapsack problem BKP removes the restriction of limiting the object by a limitation bounded by an integer c_{i}:

- maximize ∑
_{i = 1}^{not}v_{i}* x_{i} - subject to ∑
_{i = 1}^{not}v_{i}* x_{i}≤ W and x_{i}∈ {0,…, c_{i}}.

The unbounded knapsack problem UKP does not place any restrictions on the number of copies of each item.

- maximize ∑
_{i = 1}^{not}v_{i}* x_{i} - subject to ∑
_{i = 1}^{not}v_{i}* x_{i}≤ W and 0≤x_{i}.

There are many other variants of the backpack problem which are described on another page. Please refer to the Polynomial reduction.

# Resolution methods

## Greedy algorithm

The idea is to add the most effective objects as a priority, until the bag is saturated:

Sort the objects in decreasing order of efficiency w_conso: = 0foriof1Tonotifw [i] + w_conso ≤ Wsox [i]: = 1 w_conso: = w_conso + w [i]otherwisex [i]: = 0end ifend for

## Dynamic programming

The backpack problem has the property of optimal substructure, ie that we can build the optimal solution of the k-variable problem from the k - 1-variable problem.

_{k}(E) the best cost to fill a size E bag with the k

first objects. The recurrence shows that F

_{k}(E) = max {F

_{k − 1}(E), F

_{k − 1}(E - w

_{k}) + v

_{k}},

indeed the addition of a new object increases or not the best cost. If the new object is not added to the bag, F_{k}(E) is equal to F_{k − 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 it is optimal (i.e. the formula F_{k − 1}(E - w_{k})), then F_{k}(E) is equal to F_{k − 1}(E - w_{k}) + v_{k}, v_{k} being the usefulness of the new object added to the bag described above.

We therefore seek to calculate F_{not}(W), with n the total number of objects and W the maximum size of the backpack studied.

forvsof0ToWto doT [0, c]: = 0end forforiof1Tonotto doforvsof0ToWto doifc> = w [i]soT [i, c]: = max (T [i-1, c], T [i-1, cw [i]] + p [i])otherwiseT [i, c]: = T [i-1, c]end ifend forend for

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 following backpack result table:

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 elements 1 and 3 according to the second

algorithm of the backpack:

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.