Un sac avec répétitions, à la main

• Première version : $m(k,c)={\max }_{r\ge 0,r{t}_{k-1}\le c}\{r{v}_{k-1}+m(k-1,c-r{t}_{k-1})\}$, et $a(k,c)$ est le $r$ qui réalise ce maximum (le plus petit en cas d'égalité).

M[3] : [0, 0, 0, 4, 5, 7, 8, 9, 11, 12, 14, 15]
M[2] : [0, 0, 0, 4, 5, 5, 8, 9, 10, 12, 13, 14]
M[1] : [0, 0, 0, 4, 4, 4, 8, 8, 8, 12, 12, 12]
M[0] : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
A[3] : [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 2, 1]
A[2] : [0, 0, 0, 0, 1, 1, 0, 1, 2, 0, 1, 2]
A[1] : [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3]
A[0] : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Par exemple $m(3,11)=\max \{m(2,11),7+m(2,6),14+m(2,1)\}=\max \{14,15,14\}=15$, atteint pour $r=1$.

nom : M[2]
valeurs : 0 0 0 4 5 5 8 9 10 12 13 14
vert : 1 6 11
legende : cases lues pour m(3,11) : c = 11, 6 et 1 (r = 0, 1 et 2)

nom : M[3]
valeurs : 0 0 0 4 5 7 8 9 11 12 14 15
colorier : 11
legende : m(3,11) = max(14, 7 + 8, 14 + 0) = 15, atteint pour r = 1

• Seconde version : $m(k,c)=\max \{m(k-1,c),v_{k-1}+m(k,c-t_{k-1})\}$ (second terme si $t_{k-1}\le c$), calculée par $k$ puis $c$ croissants. On retrouve exactement le même tableau $M$.
• $a(3,11)=1$ : un exemplaire de l'objet $2$, on passe en $(2,6)$ ; $a(2,6)=0$ : aucun exemplaire de l'objet $1$, on passe en $(1,6)$ ; $a(1,6)=2$ : deux exemplaires de l'objet $0$. Le sac contient $2\times$ objet $0$ et $1\times$ objet $2$ : taille $6+5=11$, valeur $8+7=15$.