Somme d'un sous-ensemble⚓︎
Étant donné un ensemble \(E\) d'entiers positifs et un entier naturel \(s\), on demande s'il existe un sous-ensemble de \(E\) dont la somme des éléments est égale à \(s\).
On appelle ensemble vide l'ensemble qui ne contient aucun élément et on le note en général \(\emptyset\). L'ensemble vide est un sous-ensemble de n'importe quel ensemble \(E\) et la somme de ses éléments vaut \(0\).
Méthode par force brute : on teste tous les sous-ensembles de \(E\).
Le problème avec cette méthode est que si \(n\) est le nombre d'éléments de \(E\), alors le nombre de sous-ensembles de \(E\) est \(2^n\).
Avec le calcul des sommes de chaque sous-ensemble, on obtient un coût total de l'ordre de \(n\times 2^n\).
Ce coût est rédhibitoire. Par exemple, avec \(n=40\), le coût est d'environ \(40\times 2^{40} \simeq 4\times 10^{13}\). Donc si une machine effectue une opération en \(10^{-7}\) s, il faudra
environ \(4\times 10^6\) s pour explorer tous les cas, soit environ 1000 heures !
On va donc utiliser la programmation dynamique.
Programmation dynamique⚓︎
Un ensemble de nombres est représenté par une liste en Python, par exemple [4, 1, 8, 2].
Définition des sous-problèmes
Pour chaque élément d'indice i, nous avons une prise de décision entre deux possibilités:
-
soit on choisit cet élément d'indice
iet on continue récursivement avec les éléments restants et la somme restante; -
soit on ne le choisit pas et on continue récursivement avec les éléments restants et la même somme.
Les cas de base:
-
la somme à obtenir est nulle et le sous-ensemble est trouvé,
-
il n'y a pas d'élément à choisir ou la somme à obtenir est négative.
On utilise un dictionnaire pour mémoriser les solutions des sous-problèmes dans une approche descendante. Une clé du dictionnaire est un couple (s, i) qui représente
le sous-problème obtenir la somme s en considérant les éléments à partir de l'indice i, la valeur associée étant True ou False.
Compléter le code de la fonction somme_possible qui prend en paramètres une liste ens représentant un ensemble de nombres, un entier positif s, un indice i,
un dictionnaire memo et qui renvoie True s'il existe un sous-ensemble de nombres dont la somme des éléments vaut s et False sinon.
Exemple
>>> nombres = [4, 1, 8, 2]
>>> somme_possible(nombres, 7, 0, {})
True
Le sous-ensemble dont la somme des éléments vaut 7 est \(\{ 4, 1, 2 \}\).
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)