Hello,

Je m'intéresse au probleme suivant:
-On fournit une liste finie d'entiers (positif ou négatif)
-Ainsi qu'une somme S, un entier également.
-Le but étant de déterminer si on peut ou non obtenir S par sommation d'une partie des entiers données.

Remarque sur le probleme:
C'est une de nombreuse variante du probleme du sac à dos. Cette variante est NP-complete etc...  (donc bon bref on ne trouvera rien de trivial pour répondre a la question).

Personnellement je m'intéresse à tous les criteres rapidement calculables (en temps polynomial) permettant de déduire qu'on ne peut pas obtenir S.

Par exemple:
-Si S est strictement plus grand que la somme de tous les entiers positifs de la liste il est claire qu'on aura aucune chance d'obtenir S. (de la même manière strictement inférieur, entier négatif etc...)
-Après il y a des criteres de divisibilité du genre si S est impair et que tous les éléments de la listes sont pairs, idem on peut conclure que c'est impossible.
Ce dernier critère peut légèrement s'élargir: On choisit un entier k, on calcule le modulo k de chaque entier de la liste et de la somme, si le modulo de la somme est strictement plus grand que la somme des modulo des éléments de la liste on ne pourra pas obtenir S.

Et vous à quels critères pensez vous? Citez n'importe quel cas particuliers vous permettant de rapidement conclure qu'on ne peut pas obtenir S.