Sac à dos

Programmation dynamique • Cours-TP 2A

Problème du sac à dos

Soit un ensemble $𝒪_{n} = {o_{1}, o_{2}, \dots, o_{n}}$ de $n$ objets de valeurs $v_{1}, v_{2}, \dots, v_{n}$ et de poids respectifs $p_{1}, p_{2}, \dots, p_{n}$ .

Comment remplir un sac à dos en maximisant la valeur totale emportée $V$ tout en ne dépassant pas le poids maximal $π$ admissible par le sac à dos ? On suppose que les objets sont uniques et insécables, toutes les valeurs et tous les poids sont des entiers.

Formellement, comment maximiser $V = \sum_{o_{i} \in ℬ} v_{i}$ en respectant la contrainte $\sum_{o_{i} \in ℬ} p_{i} ⩽ π$ où $ℬ$ est l'ensemble des objets emportés dans le sac ?

Ce problème est à sous-structure optimale : on peut exprimer une solution optimale au problème en fonction des solutions optimales des sous-problèmes. La programmation dynamique est donc une option possible pour résoudre ce problème. Voici les équations de Bellman pour ce problème, où $S (n, π)$ est la solution optimale au problème du sac à dos avec n objets et un poids maximum admissible de $π$ :

S (n, π) = {\begin{matrix} 0 & si n = 0 ou si π = 0 \\ \max (v_{n} + S (n - 1, π - p_{n}), S (n - 1, π)) & si p_{n} ⩽ π \\ S (n - 1, π) & sinon \end{matrix}

Ces équations sont à interpréter comme suit :

S'il n'y a pas d'objets ou si l'on ne peut pas mettre d'objets, on ne peut pas emporter de valeur dans le sac.
Si l'objet peut être mis dans le sac, la solution optimale est le maximum de deux cas possibles :
- soit l'objet fait partie de la solution optimale.
- soit la solution optimale est obtenue sans l'objet.
Si l'objet ne peut pas être mis dans le sac, la solution optimale est obtenue sans cet objet.

En Python, on se donne une liste globale d'objets:

OBJETS = ((100, 7), (700, 15), (500, 2), (400, 9), (300, 3), (200, 2))

1

Indice

Construire une matrice de dimensions (n+1) x (pmax+1) puis remplir chaque cellule en comparant les solutions avec et sans l'objet courant.

Écrire une fonction impérative dyn_kp(pmax) qui renvoie la valeur maximale d'un sac à dos de capacité pmax contenant des objets uniques et insécables définis par leurs valeurs et poids. Cette fonction utilise la variable globale OBJETS un tableau de résolution qu'elle complète en suivant les équations de Bellman du problème. Par exemple dyn_kp(10) renvoie 1000.
2

Indice

Définir les conditions d'arrêt pour un sac vide ou sans objets puis calculer le maximum entre l'inclusion et l'exclusion de l'élément actuel.

Écrire une fonction récursive sans mémoïsation rec_kp(n, pmax) qui renvoie la valeur optimale d'un sac à dos de capacité pmax en considérant les n premiers objets disponibles. Par exemple rec_kp(6,5) renvoie 800.
3

Indice

Vérifier la présence des paramètres dans un cache avant tout calcul puis stocker le résultat obtenu pour éviter les appels redondants.

Écrire une fonction récursive avec mémoïsation mem_kp(n, pmax, S) qui renvoie la valeur optimale d'un sac à dos de capacité pmax en mémorisant les résultats intermédiaires dans le dictionnaire S passé en paramètre. Par exemple mem_kp(6, 5, {}) renvoie 800.