Sac à dos (Knapsack)

Problème d’optimisation de sélection d’objets avec contraintes de poids et valeur.

Problème de décision

• Instance :
  • Ensemble d’objets $O=\{o_1,...,o_n\}$
  • Fonction de poids $w:O\to \mathbb{N}$
  • Fonction d’utilité $u:O\to \mathbb{N}$
  • Capacité maximale $B$
  • Seuil d’utilité $k$
• Question : Existe-t-il $X\subseteq O$ tel que ${\sum }_{x\in X}w(x)\le B$ et ${\sum }_{x\in X}u(x)\ge k$ ?

Complexité

Complexité $O(n\times m)$ donc non polynomial

Sac à dos est NP-complet.

Certificat

• Certificat de verification : Sous-ensemble $X\subseteq O$
• Vérification : Calculer les sommes et vérifier les contraintes

Réductions

Partition ${\ll }_P$​ Sac à dos

$f:⟨S⟩\to ⟨O=S,w=u=S,B=k=\frac{1}{2}\sum x⟩$

Idée : Une partition équilibrée correspond à un sac avec poids = utilité = moitié de la somme totale.

Sous-somme ${\ll }_P$​ Sac à dos

Par transitivité : Sous-somme ${\ll }_P$ Partition ${\ll }_P$​ Sac à dos

Ou directement : $f:⟨S,k⟩\to ⟨O=S,w=u=S,B=k,k⟩$

Programmation dynamique

Bien que NP-complet, le sac à dos admet un algorithme pseudo-polynomial en $O(n\times B)$.

Taille de l’entrée : $n+\log B$ Complexité : $O(n\times 2^{\log B})$ donc exponentielle en la taille de l’entrée.

Self-réductibilité

Sac à dos est self-réductible.

Algorithme avec oracle

// sacadosdec(X, w, u, B, k) -> oui/non  (oracle O(1))

// Trouver k max avec dichotomie
k = 1
tant que sacadosdec(X, w, u, B, k):
    k = k+1
k = k-1  // k max trouvé

// Construire la solution
pour x ∈ X:
    si sacadosdec(X\{x}, w, u, B, k):
        X = X \ {x}
retourner X