Somme de Sous-Ensembles

Le problème de la somme de sous-ensembles (ou subset sum problem, SSP) est un problème classique en informatique théorique et en optimisation combinatoire.

Il consiste à déterminer s'il existe un sous-ensemble d'un ensemble donné de nombres entiers dont la somme est égale à une valeur cible donnée.

Formellement, étant donné un ensemble $ A = \{n_1, n_2, \ldots, n_n\} $ et une cible $ N $, le but est de trouver un sous-ensemble $ B \subseteq A $ tel que la somme des éléments de $ B $ soit égale à $ N $ soit $ \sum n_{i \subseteq B} = N $

— Approche naïve (force brute) : tester toutes les combinaisons possibles de sous-ensembles. Cette méthode a une complexité exponentielle $ O(2^n) $, ce qui la rend inefficace pour de grands ensembles

— Programmation dynamique : Utiliser une table pour stocker les sommes réalisables avec les sous-ensembles. La complexité est $ O(n \times N) $, où $ n $ est la taille de l'ensemble et $ N $ est la valeur cible.

— Algorithmes d'approximation : Pour des instances de grande taille, des algorithmes comme le Meet-in-the-Middle réduisent la complexité à $ O(2^{n/2}) $

Le problème du sac à dos généralise la somme de sous-ensembles en associant un poids et une valeur à chaque élément.

Dans le sac à dos, l'objectif est de maximiser la valeur totale sans dépasser une capacité donnée, alors que la somme de sous-ensembles se concentre uniquement sur la somme des éléments.

En autorisant la répétition des éléments dans la somme de sous-ensembles, alors le problème des sous-ensemble est une variante des partitions d'entiers restreinte à un ensemble donné.