Qu'est-ce que le problème du sac à dos ?
Imagine que tu prépares ton sac pour un voyage en randonnée. Tu as une liste d'objets (une lampe, une gourde, un livre, etc.), chacun avec un poids et une valeur d'utilité. Ton sac a une capacité maximale, par exemple 10 kg. Le but ? Choisir les objets à emporter pour maximiser la valeur totale sans dépasser le poids autorisé. C'est exactement le problème du sac à dos 0/1, un classique de l'algorithmique et de la NSI.
Ce problème est dit "NP-difficile", ce qui signifie qu'il n'existe pas d'algorithme simple et rapide pour le résoudre exactement pour un grand nombre d'objets. C'est là qu'intervient une technique puissante : la programmation dynamique. Elle permet de trouver la solution optimale sans tester toutes les combinaisons (ce qui serait beaucoup trop long), en décomposant le problème en sous-problèmes plus petits.
Le principe de la programmation dynamique
La programmation dynamique est une méthode d'optimisation qui consiste à résoudre un problème complexe en le divisant en sous-problèmes plus simples, à résoudre chacun une seule fois, et à stocker leurs solutions pour les réutiliser. C'est une alternative à la récursivité naïve qui recalcule souvent les mêmes résultats.
Pour le sac à dos, l'idée géniale est de construire un tableau (ou matrice) DP.
- Les lignes représentent les objets considérés un par un (de 0 à n).
- Les colonnes représentent les capacités de sac possibles (de 0 à capacité max).
- La cellule
DP[i][w]contiendra la valeur maximale que l'on peut obtenir avec les i premiers objets pour un sac de capacité w.
On remplit ce tableau ligne par ligne, en se posant à chaque étape une question simple : "Est-ce que je prends le i-ème objet ou pas ?" La réponse est le maximum entre ces deux options.
Implémentation en Python pas à pas
Passons à la pratique ! Voici une implémentation commentée de l'algorithme du sac à dos en programmation dynamique.
Définition des données
On commence par définir nos objets et la capacité du sac.
# Exemple pour la NSI
poids = [2, 3, 4, 5] # Poids de chaque objet
valeurs = [3, 4, 5, 6] # Valeur de chaque objet
capacite_max = 8 # Capacité totale du sac
Construction du tableau DP
On initialise un tableau de (n+1) lignes et (capacite_max+1) colonnes, rempli de zéros.
n = len(poids)
DP = [[0 for _ in range(capacite_max + 1)] for _ in range(n + 1)]
Le cœur de l'algorithme
On remplit le tableau avec une double boucle.
for i in range(1, n + 1):
for w in range(1, capacite_max + 1):
# Si le poids de l'objet courant est inférieur à la capacité courante
if poids[i-1] <= w:
# On prend le MAX entre :
# 1. Ne pas prendre l'objet -> valeur précédente
# 2. Prendre l'objet -> valeur de l'objet + meilleure valeur pour le poids restant
DP[i][w] = max(DP[i-1][w], valeurs[i-1] + DP[i-1][w - poids[i-1]])
else:
# On ne peut pas prendre l'objet, on garde la valeur précédente
DP[i][w] = DP[i-1][w]
À la fin, DP[n][capacite_max] contient la valeur optimale !
Récupération des objets choisis
Pour savoir quels objets forment cette solution optimale, on doit "remonter" dans le tableau.
w = capacite_max
objets_choisis = []
for i in range(n, 0, -1):
if DP[i][w] != DP[i-1][w]: # L'objet i a été pris
objets_choisis.append(i-1) # On stocke l'indice
w -= poids[i-1] # On soustrait son poids
Complexité et applications réelles
La complexité de cet algorithme est en O(n * C), où n est le nombre d'objets et C la capacité maximale. C'est une complexité pseudo-polynomiale. Elle est efficace si la capacité C n'est pas un nombre astronomique.
Ce problème n'est pas qu'un exercice académique ! Il a de nombreuses applications :
- Logistique : Chargement de camions ou de conteneurs.
- Finance : Sélection de projets d'investissement avec un budget limité.
- Informatique : Allocation de ressources (mémoire, CPU).
- Cryptographie : Dans certains systèmes de chiffrement.
Variantes du problème à explorer
Une fois que tu maîtrises la version 0/1 (un objet est pris ou pas), tu peux explorer d'autres variantes :
- Sac à dos fractionnaire : Tu peux prendre une fraction d'un objet (résolu par un algorithme glouton).
- Sac à dos avec répétition : Tu as un nombre illimité de chaque objet.
- Sac à dos multidimensionnel : Plusieurs contraintes (poids ET volume).
N'hésite pas à coder ces variantes pour approfondir ta compréhension !
