Une seule ligne suffit

• La ligne $k$ de $M$ ne dépend que de la ligne $k-1$. On garde deux tableaux prec et cour de $C+1$ cases, que l'on échange à chaque $k$ : mémoire $\Theta (C)$ au lieu de $\Theta (nC)$, temps toujours $\Theta (nC)$.
• Dans un seul tableau $L$, au début du tour $k$, $L$ contient la ligne $k-1$. Pour calculer la nouvelle valeur de $L[c]$, il faut l'ancienne valeur de $L[c]$ et l'ancienne valeur de $L[c-t]$, avec $t=T[k-1]>0$. Si l'on parcourt les $c$ par valeurs décroissantes, la case $c-t<c$ n'a pas encore été modifiée pendant ce tour : elle contient bien $m(k-1,c-t)$.

static int uneLigne(int[] V, int[] T, int C) {
    int[] L = new int[C + 1];                   // ligne 0 : que des zéros
    for (int k = 1; k < V.length + 1; k++)
        // invariant : L[0:c+1] est la ligne k-1, L[c+1:C+1] est la ligne k
        for (int c = C; c >= T[k-1]; c--)
            L[c] = Math.max(L[c], V[k-1] + L[c - T[k-1]]);
    return L[C];                                  // L est la ligne n
}

Les cases $c<T[k-1]$ ne changent pas : $m(k,c)=m(k-1,c)$.

nom : L
valeurs : 0 0 0 4 4 4 4 9 9 11 11
colorier : 6
vert : 7..10
fleches : 4->6:+5
zone : 0..6 ligne 2
zone : 7..10 ligne 3
legende : exemple du cours, tour k = 3 (t = 2), c = 6 : L[4] vaut encore m(2,4)

• Par $c$ croissants, $L[c-t]$ a déjà été mis à jour pendant le tour $k$ : il peut contenir l'objet $k-1$, que l'on ajoute alors une deuxième fois. On calcule le sac avec répétitions du chapitre 3. Sur l'exemple, la version décroissante donne $13$ (le bon résultat) et la version croissante $25$ (cinq exemplaires de l'objet de taille $2$ et de valeur $5$).

nom : L
valeurs : 0 0 5 5 10 10 4 4 4 11 11
colorier : 6
vert : 2..5
fleches : 4->6:+5
zone : 2..5 déjà modifiées
zone : 6..10 ligne 2
legende : par c croissants, L[4] = 10 compte déjà deux fois l'objet 2