Sacs à dos

Dans ce TD nous allons implanter des algorithmes pour résoudre le problème de la somme de sous-ensembles (Subset sum), aussi connu sous le nom de problème du sac à dos. On rappelle le problème : étant donné un ensemble d’entiers positifs , et un entier , déterminer s’il existe un sous-ensemble tel que

Un algorithme naïf

On va commencer avec un algorithme naïf : on énumère tous les sous-ensembles de , jusqu’à en trouver un qui somme à .

: Écrire une fonction subset_sum(S, t) qui prend en entrée une liste d’entiers positifs S, un entier positif t, et qui renvoie True si le problème a une solution, en utilisant l’algorithme naïf décrit plus haut.

Un algorithme récursif pour le problème d’optimisation

Le problème d’optimisation associé à la paire , consiste à trouver le sous-ensemble qui maximise la valeur sous la contrainte .

Pour , on définit la valeur comme étant la solution du problème d’optimisation associé à  :

: Écrire une fonction partial_subset_sum(S, i, t) qui calcule à l’aide de deux appels récursifs à partial_subset_sum(S, i-1, ...).

: Récrire subset_sum(S, t) pour qu’il fasse appel à partial_subset_sum.

Amélioration par programmation dynamique

Les appels récursifs de la partie précédente passent beaucoup de temps à recalcuer les valeurs . Par les techniques de mémoisation et de la programmation dynamique, nous pouvons mémoriser ces appels et réutiliser les résultats pour les appels suivants.

L’idée de la mémoisation consiste à calculer, à la place de , toute la liste définie comme suit :

Les deux appels récursifs de l’algorithme précedent, sont donc remplacés par un appel récursif qui calcule , suivi par le calcul de

L’ensemble sera alors obtenu en fusionnant et . La fusion est facilitée on fait attention à garder les deux listes ordonnées (comparer avec le tri fusion).

(mémoisation) : Écrire une variante partial_subset_sum_memo qui procède comme décrit ci-dessus, en calculant les listes par un appel récursif.

: Écrire une variante partial_subset_sum_dyn sans appels récursifs.

: Utiliser les techniques de mesure des performances vues au TD sur l’algèbre linéaire pour comparer les performances de vos algorithmes.