Sac à dos

Etant donné un ensemble $A = \{a_1, \ldots, a_n\}$, des poids positifs $\{p_i \vert i \in \{1, \ldots, n\}\}$, des valeurs positives $\{v_i \vert i \in \{1, \ldots, n\}\}$, et une constante positive $K$. Une solution réalisable est un sous-ensemble $I$ de $\{1, \ldots, n\}$ tel que $$\sum_{i \in I}p_i \leq K$$, la valeur de la fonction objectif est $$\sum_{i \in I}v_i$$. Le problème du sac à dos est le suivant :

• données : un ensemble $A$ muni de deux valuations $\{p_i \vert i \in \{1, \ldots, n\}\}$ et $\{v_i \vert i \in \{1, \ldots, n\}\}$, et une constante $K>0$
• question : trouver le sous ensemble $B$ de $A$ maximisant $$\sum_{i \in I}v_i$$ sous la contrainte $$\sum_{i \in I}p_i \leq K$$.

Ce problème est NP-Complet.