Le sens d'une boucle décide du problème résolu

/* (A) */  for (int i = 0; i < n; i++)
               for (int c = C; c >= p[i]; c--)
                   if (v[i] + m[c - p[i]] > m[c]) { m[c] = v[i] + m[c - p[i]]; }

/* (B) */  for (int i = 0; i < n; i++)
               for (int c = p[i]; c <= C; c++)
                   if (v[i] + m[c - p[i]] > m[c]) { m[c] = v[i] + m[c - p[i]]; }

(A) résout le sac à dos du chapitre (chaque objet au plus une fois). (B) résout le sac à dos illimité, où chaque objet peut être pris autant de fois qu'on veut. Et rien, dans le code, ne le dit.

Pourquoi. La ligne $m$ tient à la fois l'ancienne ligne $M[i-1]$ et la nouvelle $M[i]$. Quand on lit m[c - p[i]] :

• en décroissant, la case $c-p_i$ est à gauche de $c$, donc pas encore réécrite pendant ce tour $i$ : elle contient $M[i-1][c-p_i]$. C'est bien la récurrence du chapitre, qui interdit de reprendre l'objet $i$.
• en croissant, la case $c-p_i$ a déjà été mise à jour pendant ce tour $i$ : elle contient $M[i][c-p_i]$, donc une valeur qui a peut-être déjà pris l'objet $i$. On l'autorise à le reprendre.

Mesure, avec deux objets $p=(2,3)$, $v=(3,4)$ :

C=4   (A) decroissant = 4    (B) croissant = 6
C=5   (A) decroissant = 7    (B) croissant = 7
C=6   (A) decroissant = 7    (B) croissant = 9
C=7   (A) decroissant = 7    (B) croissant = 10

À $C=6$, (A) rend $7$ (les deux objets, poids $5$) et (B) rend $9$ (trois fois l'objet de poids $2$). À $C=5$ les deux coïncident, ce qui est le pire cas pour le testeur : un jeu de tests limité à $C=5$ n'aurait rien vu. Le chapitre chap:discipline le dit autrement : on teste aux frontières, et ici la frontière est la capacité où reprendre un objet devient possible.

À retenir. Une réduction de mémoire n'est jamais neutre. Ici elle ne change pas la complexité en temps, mais elle rend le sens de la boucle sémantique : la même ligne de code résout deux problèmes différents selon un signe. Quand on écrase la table, on écrit l'ordre de parcours dans un commentaire, au-dessus de la boucle.