Deux sacs : le tableau des choix

• On applique l'hérédité à trois cas du cours :

• $m(0,5,6)=0$ (base) ;
• $m(1,5,6)=4$ : l'objet $0$ (taille $4$) va dans $S_0$ (cas $1$, premier cas trouvé en cas d'égalité) ;
• $m(2,5,6)=7$ : l'objet $1$ (taille $3$) va dans $S_0$ avec $m(1,2,6)=4$ (l'objet $0$ dans $S_1$) ;
• $m(3,5,6)=10$ : l'objet $2$ va dans $S_1$, avec $m(2,5,3)=7$ ;
• $m(4,5,6)=10$ : l'objet $3$ (taille $2$) ne fait pas mieux : cas $0$.

• On remplit $A$ en même temps que $M$ :

M[k][c0][c1] = M[k-1][c0][c1]; A[k][c0][c1] = 0;          // dans aucun sac
if (t <= c0 && v + M[k-1][c0-t][c1] > M[k][c0][c1]) {
    M[k][c0][c1] = v + M[k-1][c0-t][c1]; A[k][c0][c1] = 1; // dans S0
}
if (t <= c1 && v + M[k-1][c0][c1-t] > M[k][c0][c1]) {
    M[k][c0][c1] = v + M[k-1][c0][c1-t]; A[k][c0][c1] = 2; // dans S1
}

puis l'affichage n'a plus besoin de $M$ :

static void acsm(int[][][] A, int[] V, int[] T, int k, int c0, int c1) {
    if (k == 0) return;                                 // sacs vides
    int a = A[k][c0][c1], t = T[k-1];
    if (a == 0) acsm(A, V, T, k-1, c0, c1);
    else if (a == 1) { acsm(A, V, T, k-1, c0-t, c1); System.out.printf("objet %d -> S0%n", k-1); }
    else { acsm(A, V, T, k-1, c0, c1-t); System.out.printf("objet %d -> S1%n", k-1); }
}

Il affiche l'objet $0$ dans $S_0$ et les objets $1$ et $2$ dans $S_1$, pour une valeur $10$.

• On peut supposer $c_0\le c_1$ et ne calculer que ces cases : pour $c_0>c_1$, on lit $M[k][c_1][c_0]$. Lorsque $C_0=C_1$, cela divise par deux environ la mémoire (et le temps) ; en Java, on alloue des lignes de longueurs différentes (tableau « en triangle »). Si $C_0\ne C_1$, le gain se limite au carré $[0:C_0+1{]}^2$.