Problème du Sac à Dos (Knapsack)

1. Histoire et Contexte

Le problème du sac à dos est l'un des problèmes fondateurs de l'optimisation combinatoire. Son nom imagé a été popularisé dans les années 1930 par le mathématicien Tobias Dantzig (le père de George Dantzig). L'idée est intuitive : un randonneur (ou un cambrioleur) possède un sac de capacité limitée. Il a devant lui plusieurs objets ayant chacun un poids et une valeur. Comment maximiser la valeur emportée sans déchirer le sac ?

Le problème dépasse largement le cadre du randonneur. Il modélise l'allocation de ressources sous contrainte : sélection de projets d'investissement sous contrainte de budget, découpe de matériaux industriels, ou chargement de navires cargos.

Plus étonnant encore, le sac à dos a été la base du premier système de cryptographie asymétrique (à clé publique) inventé par Merkle et Hellman en 1978. Leur idée : si le problème est NP-difficile, on peut s'en servir pour cacher un message ! (Ce cryptosystème a finalement été cassé par Adi Shamir quelques années plus tard, mais a ouvert la voie au système RSA).

2. Définition Mathématique

Problème d'optimisation (0/1 Knapsack) :
Soient $n$ objets. Chaque objet $i$ possède un poids $w_i > 0$ et une valeur (ou profit) $v_i > 0$. Soit $W$ la capacité maximale du sac.
On cherche le vecteur d'indicateurs $X = (x_1, \dots, x_n) \in \{0,1\}^n$ maximisant la fonction objectif : $$ \max \sum_{i=1}^n v_i x_i $$ Sous la contrainte de capacité : $$ \sum_{i=1}^n w_i x_i \le W $$

3. La classe $\mathcal{NP}$ et le paradoxe Pseudo-Polynomial

Une complexité exponentielle : l'arbre des choix

Puisque chaque objet peut être pris ($x_i=1$) ou laissé ($x_i=0$), il y a $2^n$ combinaisons possibles (le cardinal de l'ensemble des parties $\mathcal{P}(\{1..n\})$).

n objets	Combinaisons ($2^n$)	Temps (1ns / comb.)
20	1 048 576	< 2 ms
40	1,09 × 10¹²	18 minutes
60	1,15 × 10¹⁸	36 ans
80	1,20 × 10²⁴	38 000 ans

La force brute est en $\mathcal{O}(2^n)$.

NP-complet, oui... mais "Faiblement" !

La version décision du problème ("Peut-on atteindre une valeur $\ge K$ sans dépasser le poids $W$ ?") est NP-complète. Le certificat est simplement la liste des objets choisis (ex: [1, 0, 1, 1, 0]), vérifiable en temps polynomial $\mathcal{O}(n)$ par de simples additions.

Cependant, il y a une subtilité majeure (niveau L3) : Contrairement au Voyageur de Commerce, le Sac à dos peut être résolu de manière exacte par Programmation Dynamique en temps $\mathcal{O}(n \times W)$.

Puisque la complexité dépend de la valeur de $W$ (et non de la taille de son codage binaire en mémoire qui est $\log_2(W)$), on dit que l'algorithme est pseudo-polynomial. Le Sac à dos est donc dit faiblement NP-complet : en pratique, si la capacité $W$ n'est pas un nombre astronomique, un ordinateur le résout en une fraction de seconde !

Exercice : Incarnez le Vérificateur (Version Décision)

Cliquez sur les objets pour les placer dans votre sac. Votre objectif : Trouver un certificat prouvant qu'il est possible d'atteindre la Valeur Cible (K) sans faire craquer le sac (Poids $\le W$).

Choisissez une instance :

Poids du sac : 0 / 0 kg

0%

Valeur acquise : 0 €
Objectif (K) : 0 €