Des jetons dans des boîtes

• Avec $0$ boîte, on ne peut placer aucun jeton : $M(0,0)=0$ et $M(0,q)=-\infty$ pour $q>0$ (répartition impossible). Supposons le problème résolu : la $k$-ème boîte (numéro $k-1$) reçoit $x$ jetons, avec $0\le x\le \min (q,Q)$, et les $q-x$ autres sont répartis de façon optimale dans les $k-1$ premières boîtes.

Base. $M(0,0)=0$ ; $\forall q,1\le q<m+1$ : $M(0,q)=-\infty$.

Hérédité. $\forall k,1\le k<n+1$, $\forall q,0\le q<m+1$ :

$$M(k,q)=\underset{0\le x<\min (q,Q)+1}{\max }\{g_{k-1}(x)+M(k-1,q-x)\}.$$

• On représente $-\infty$ par Integer.MIN_VALUE / 2, qui reste très négatif quand on lui ajoute un gain.

static int[][][] calculerMA(int[][] G, int m) {
    int n = G.length, Q = G[0].length - 1;
    final int MOINS_INFINI = Integer.MIN_VALUE / 2;
    int[][] M = new int[n + 1][m + 1], A = new int[n + 1][m + 1];
    for (int q = 1; q < m + 1; q++) M[0][q] = MOINS_INFINI; // base
    for (int k = 1; k < n + 1; k++)                       // par k croissants
        for (int q = 0; q < m + 1; q++) {
            M[k][q] = MOINS_INFINI;
            for (int x = 0; x < Math.min(q, Q) + 1; x++) { // x jetons dans la k-ème boîte
                int v = G[k - 1][x] + M[k - 1][q - x];
                if (v > M[k][q]) { M[k][q] = v; A[k][q] = x; }
            }
        }                                     // M[k][q] = M(k,q), A[k][q] = arg M(k,q)
    return new int[][][] {M, A};
}

static void aro(int[][] A, int[][] G, int k, int q) {
    if (k == 0) return;                   // aucune boîte : rien à afficher
    int x = A[k][q];                      // jetons de la k-ème boîte
    aro(A, G, k - 1, q - x);              // répartition des q-x autres affichée
    System.out.printf("  boîte %d <-- %d jetons, gain %d%n", k - 1, x, G[k - 1][x]);
}                                         // donc répartition (k,q) affichée

• La boîte $0$ ne peut pas recevoir plus de $Q=4$ jetons : placer $5$ ou $6$ jetons dans la seule première boîte est impossible, d'où $M(1,5)=M(1,6)=-\infty$. L'exécution donne :

nom : M[1]
valeurs : 0 0 80 90 90 -∞ -∞
griser : 5 6
legende : la boîte 0 seule (Q = 4) ne peut pas recevoir 5 ou 6 jetons

M[3] = [0, 20, 80, 100, 120, 140, 160]
M[2] = [0, 10, 80, 90, 100, 120, 130]
M[1] = [0, 0, 80, 90, 90, -oo, -oo]
M[0] = [0, -oo, -oo, -oo, -oo, -oo, -oo]
Gain maximum M(3,6) = 160
  boîte 0 <-- 2 jetons, gain 80
  boîte 1 <-- 0 jetons, gain 0
  boîte 2 <-- 4 jetons, gain 80

Le glouton, lui, place les quatre premiers jetons dans la boîte $2$ (gain marginal $20$ contre $0$ et $10$), puis deux dans la boîte $1$ : gain $100$ seulement.

• Pour chaque case $(k,q)$, la boucle sur $x$ fait au plus $\min (q,Q)+1\le Q+1$ tours : le calcul est en $\Theta (nmQ)$ dans le pire cas, l'affichage en $\Theta (n)$.