Dans ce chapitre, on recherche des algorithmes pour résoudre des problèmes se présentant sous la forme suivante:
On se donne un ensemblefini et à chaque élément
de
(en général, un entier positif), on se donne de plus un prédicat (une fonction à valeurs {vrai, faux})
sur l'ensemble des parties de
de
est satisfait
soit maximal (ou minimal, dans certains cas)
Les méthodes développées pour résoudre ces problèmes sont de
natures très diverses. Pour certains exemples, il existe un algorithme
très simple consistant à initialiser par 
, puis à
ajouter successivement des éléments suivant un certain critère,
jusqu'à obtenir la solution optimale, c'est ce qu'on appelle l'algorithme glouton. Tous les problèmes ne sont pas résolubles
par l'algorithme glouton mais, dans le cas où il s'applique, il est
très efficace. Pour d'autres problèmes, c'est un algorithme
dit de programmation dynamique qui permet d'obtenir la solution,
il s'agit alors d'utiliser certaines particularités de la solution
qui permettent de diviser le problème en deux; puis de résoudre
séparément chacun des deux sous-problèmes, tout en conservant en
table certaines informations intermédiaires. Cette technique, bien
que moins efficace que l'algorithme glouton, donne quand même un
résultat intéressant car l'algorithme mis en 
uvre est en général
polynomial. Enfin, dans certains cas, aucune des deux méthodes
précédentes ne donne de résultat et il faut alors utiliser des
procédures d'exploration systématique de l'ensemble de toutes les
parties de satisfaisant , cette exploration systématique est
souvent appelée exploration arborescente (ou backtracking en anglais).