Au plus $K$ entrepôts approvisionnés

• Supposons le problème résolu. Ou bien le $k$-ème entrepôt ne reçoit rien, et les $k-1$ premiers se partagent le stock $s$ avec au plus $u$ livraisons ; ou bien il reçoit $s^{\prime }\ge 1$ unités, ce qui consomme un camion.

Base. $m(0,s,u)=0$ pour tous $s$ et $u$.

Hérédité. $\forall k,1\le k<n+1$, $\forall s$, $\forall u,0\le u<K+1$ :

$$m(k,s,u)=\max (m(k-1,s,u),\underset{1\le s^{\prime }<s+1,u\ge 1}{\max }\{g(k-1,s^{\prime })+m(k-1,s-s^{\prime },u-1)\left\}\right).$$

• Le tableau a trois dimensions ; l'argument $a(k,s,u)$ indique la livraison du $k$-ème entrepôt, et l'on décrémente $u$ seulement si elle est non nulle.

static int[][][] calculer(int[][] G, int K, int[][][] A) {
    int n = G.length, S = G[0].length - 1;
    int[][][] M = new int[n + 1][S + 1][K + 1];             // base : M[0][s][u] = 0
    for (int k = 1; k < n + 1; k++)
        for (int s = 0; s < S + 1; s++)
            for (int u = 0; u < K + 1; u++) {
                M[k][s][u] = M[k - 1][s][u]; A[k][s][u] = 0;     // rien au k-ème
                if (u > 0)
                    for (int sp = 1; sp < s + 1; sp++) {         // livraison non nulle
                        int v = G[k - 1][sp] + M[k - 1][s - sp][u - 1];
                        if (v > M[k][s][u]) { M[k][s][u] = v; A[k][s][u] = sp; }
                    }
            }
    return M;
}

static void afficher(int[][][] A, int[][] G, int k, int s, int u) {
    if (k == 0) return;
    int a = A[k][s][u];
    afficher(A, G, k - 1, s - a, a > 0 ? u - 1 : u);   // les k-1 premiers affichés
    if (a > 0) System.out.printf(" %d<--%d", k - 1, a); // puis le k-ème
}

-

K = 0 : gain maximum 0 :
K = 1 : gain maximum 5 : 0<--4
K = 2 : gain maximum 9 : 0<--4 2<--1
K = 3 : gain maximum 10 : 0<--3 2<--1 3<--1
K = 4 : gain maximum 10 : 0<--3 2<--1 3<--1

Au-delà de trois camions, la contrainte ne joue plus : la répartition optimale du chapitre n'approvisionne que trois entrepôts.

• Il y a $(n+1)(S+1)(K+1)$ cases, chacune demandant au plus $S$ essais : $\Theta (nK{S}^2)$.