Le problème du sac à dos 0/1 : un code en Python
Le problème du sac à dos 0/1 est un problème classique en optimisation combinatoire. Il consiste à déterminer le sous-ensemble d'éléments à prendre dans un sac à dos, sachant que chaque élément a un poids et une valeur, et que la capacité du sac à dos est limitée. L'objectif est de maximiser la valeur totale des éléments choisis, sans dépasser la capacité du sac à dos.
Explication du code
Voici un code Python qui résout le problème du sac à dos 0/1 en utilisant la programmation dynamique :
def knapsack_0_1(capacite, poids, valeurs):
"""
Résout le problème du sac à dos 0/1 en utilisant la programmation dynamique.
Args:
capacite: La capacité du sac à dos.
poids: Une liste des poids des éléments.
valeurs: Une liste des valeurs des éléments.
Returns:
La valeur maximale des éléments qui peuvent être placés dans le sac à dos.
"""
n = len(valeurs)
# Créer une table 2D pour stocker les résultats intermédiaires.
table = [[0 for _ in range(capacite + 1)] for _ in range(n + 1)]
# Boucle sur chaque élément.
for i in range(1, n + 1):
# Boucle sur chaque capacité possible.
for w in range(1, capacite + 1):
# Si le poids de l'élément actuel est inférieur ou égal à la capacité actuelle.
if poids[i - 1] <= w:
# Prendre le maximum entre inclure l'élément ou ne pas l'inclure.
table[i][w] = max(valeurs[i - 1] + table[i - 1][w - poids[i - 1]], table[i - 1][w])
# Sinon, ne pas inclure l'élément.
else:
table[i][w] = table[i - 1][w]
# Retourner la valeur maximale.
return table[n][capacite]
# Exemple d'utilisation
valeurs = [60, 100, 120]
poids = [10, 20, 30]
capacite = 50
# Résoudre le problème du sac à dos 0/1.
valeur_maximale = knapsack_0_1(capacite, poids, valeurs)
# Afficher la valeur maximale.
print("La valeur maximale est :", valeur_maximale)
Comment le code fonctionne
Le code utilise une table 2D pour stocker les résultats intermédiaires. La première ligne et la première colonne de la table sont initialisées à 0, car il n'y a pas d'éléments ou de capacité dans ces cas.
La boucle externe parcourt chaque élément, et la boucle interne parcourt chaque capacité possible. À chaque étape, le code compare deux options :
- Inclure l'élément actuel : dans ce cas, la valeur de la cellule actuelle est la somme de la valeur de l'élément actuel et de la valeur de la cellule précédente dans la table, en soustrayant le poids de l'élément actuel de la capacité actuelle.
- Ne pas inclure l'élément actuel : dans ce cas, la valeur de la cellule actuelle est simplement la valeur de la cellule précédente dans la table.
Le code sélectionne la meilleure option et stocke la valeur dans la table. Une fois que toutes les cellules de la table ont été remplies, la valeur dans la dernière cellule de la table représente la valeur maximale des éléments qui peuvent être placés dans le sac à dos.
Conclusion
Ce code est un exemple de la façon de résoudre le problème du sac à dos 0/1 en utilisant la programmation dynamique. Il peut être utilisé pour résoudre divers problèmes d'optimisation dans de nombreux domaines, tels que la planification de la production, la gestion des stocks et l'allocation de ressources.