Livraisons minimales

• La $k$-ème livraison $s^{\prime }$ doit vérifier $b_{k-1}\le s^{\prime }\le s$, et le reste $s-s^{\prime }$ doit pouvoir être réparti en respectant les contraintes des $k-1$ premiers entrepôts. On note $m(k,s)=-\infty$ s'il n'existe aucune répartition admissible.

Base. $\forall s,0\le s<S+1$ : $m(0,s)=0$.

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

$$m(k,s)=\underset{b_{k-1}\le s^{\prime }<s+1}{\max }\{g(k-1,s^{\prime })+m(k-1,s-s^{\prime })\},$$

le maximum d'un ensemble vide valant $-\infty$.

• Seule la boucle sur $s^{\prime }$ change ; on ignore les sous-problèmes impossibles.

for (int k = 1; k < n + 1; k++)
    for (int s = 0; s < S + 1; s++) {
        M[k][s] = MOINS_INFINI;                         // aucune répartition admissible
        for (int sp = B[k - 1]; sp < s + 1; sp++) {     // sp >= b(k-1)
            if (M[k - 1][s - sp] <= MOINS_INFINI / 2) continue; // reste impossible
            int v = G[k - 1][sp] + M[k - 1][s - sp];
            if (v > M[k][s]) { M[k][s] = v; A[k][s] = sp; }
        }
    }

Avec $b=[0,3,0,1]$ :

M[4] = [-oo, -oo, -oo, -oo, 5, 9]
M[3] = [-oo, -oo, -oo, 3, 7, 9]
M[2] = [-oo, -oo, -oo, 3, 5, 6]
M[1] = [0, 2, 3, 4, 5, 5]
M[0] = [0, 0, 0, 0, 0, 0]
m(4,5) = 9
  entrepôt 0 <-- 0, gain 0
  entrepôt 1 <-- 3, gain 3
  entrepôt 2 <-- 1, gain 4
  entrepôt 3 <-- 1, gain 2

Le gain passe de $10$ (sans contrainte) à $9$ : imposer trois unités à l'entrepôt $1$, peu rentable, coûte une unité de gain.

• Si ${\sum }_i{b}_i>S$, aucune répartition n'est admissible et $m(n,S)=-\infty$ : le programme le détecte (essai avec $b=[2,2,1,1]$), et l'appel de aro n'a alors aucun sens.