Le même sous-problème, vingt-deux millions de fois

Instance choisie pour être la pire : $n$ objets de poids $1$, de valeurs $1,2,\dots ,n$, capacité $C=n/2$.

Lecture. À $n=24$, l'algorithme fait vingt-deux millions d'appels pour ne rencontrer que deux cent quarante-sept situations différentes. Chaque situation est donc recalculée, en moyenne, quatre-vingt-neuf mille fois — et le calcul recommencé est identique à chaque fois, puisqu'il ne dépend que de $(c,i)$.

Le nombre de couples est borné par $(C+1)(n+1)$, soit ici $13\times 25=325$, dont $247$ sont effectivement atteints. C'est polynomial en $n$ et $C$, tandis que le nombre d'appels est exponentiel.

Ce que cela annonce. Retenir le résultat de chaque couple dans une table, et le relire au lieu de le recalculer, ramène le coût au nombre de couples : $\Theta (nC)$. C'est exactement la programmation dynamique du chapitre chap:dynamique — et l'écart mesuré ici, $88978$, est la raison d'être de ce chapitre.

Un mot de prudence. $\Theta (nC)$ n'est pas polynomial en la taille de l'entrée : $C$ s'écrit avec $\log C$ chiffres. On dit que ce coût est pseudo-polynomial. Si $C$ vaut $10^{12}$, la table est hors de portée et le retour sur trace redevient préférable. Aucune des deux méthodes ne domine l'autre : le chapitre chap:probabilistes en dresse le bilan complet.