Le cambrioleur prudent

• Le glouton prend la maison $1$ (butin $9$), ce qui interdit les maisons $0$ et $2$ ; puis la maison $4$ ($8$), ce qui interdit $3$ et $5$. Butin $17$. Or les maisons $0$, $2$, $4$ donnent $6+6+8=20$.

nom : x
valeurs : 6 9 6 1 8 7
colorier : 1 4
griser : 0 2 3 5
legende : glouton : maisons 1 et 4, butin 9 + 8 = 17

nom : x
valeurs : 6 9 6 1 8 7
vert : 0 2 4
legende : optimum : maisons 0, 2 et 4, butin 6 + 6 + 8 = 20

• Supposons le problème résolu sur les $k$ premières maisons. Ou bien la maison $k-1$ n'est pas visitée, et le butin est $m(k-1)$ ; ou bien elle l'est, la maison $k-2$ ne l'est pas, et le butin est $x_{k-1}+m(k-2)$. Base : $m(0)=0$, $m(1)=x_0$. Hérédité : $\forall k,2\le k<n+1$,

$$m(k)=\max \{m(k-1),x_{k-1}+m(k-2)\}.$$

-

static int[] calculerM(int[] x) { int n = x.length;
    int[] M = new int[n + 1];
    M[0] = 0;                                   // base
    if (n > 0) M[1] = x[0];
    for (int k = 2; k < n + 1; k++)             // hérédité
        M[k] = Math.max(M[k-1], M[k-2] + x[k-1]);
    return M;
}
static void amaisons(int[] M, int[] x, int k) {
    // affiche les maisons visitées parmi les k premières
    if (k <= 0) return;
    if (k == 1) { if (M[1] > 0) System.out.print(" 0"); return; }
    if (M[k] == M[k-1]) amaisons(M, x, k-1);    // la maison k-1 n'est pas visitée
    else { amaisons(M, x, k-2); System.out.print(" " + (k-1)); }
}

x = [6, 9, 6, 1, 8, 7]
glouton (plus grande valeur disponible d'abord) : 17
M = [0, 6, 9, 12, 12, 20, 20]
somme maximum 20 : maisons 0 2 4

nom : M
valeurs : 0 6 9 12 12 20 20
colorier : 6
vert : 1 3 5
fleches : 6->5 5->3:+8 3->1:+6
legende : remontée : M[6] = M[5], puis maisons 4 (+8), 2 (+6) et 0 (+6)

Le calcul et l'affichage sont en $\Theta (n)$.