Le glouton du gain marginal

On maintient le nombre $q_{i}$ de jetons de chaque boîte.


static int glouton(int[][] G, int m) {
    int n = G.length, Q = G[0].length - 1;
    int[] q = new int[n];                  // q[i] : jetons déjà dans la boîte i
    for (int j = 0; j < m; j++) {          // j jetons ont été placés
        int b = -1;                        // boîte non pleine de plus grand gain marginal
        for (int i = 0; i < n; i++)
            if (q[i] < Q && (b == -1 ||
                G[i][q[i] + 1] - G[i][q[i]] > G[b][q[b] + 1] - G[b][q[b]]))
                b = i;
        q[b]++;
    }
    int gain = 0;
    for (int i = 0; i < n; i++) gain += G[i][q[i]];
    return gain;
}

Complexité : $Θ (m n)$ .

Le gain d'une répartition $(q_{0}, \dots, q_{n - 1})$ est la somme des gains marginaux des jetons placés : $\sum_{i} g_{i} (q_{i}) = \sum_{i} \sum_{j = 0}^{q_{i} - 1} δ_{i} (j)$ , où $δ_{i} (j) = g_{i} (j + 1) - g_{i} (j)$ . Si les gains sont concaves, chaque suite $δ_{i} (0) \geq δ_{i} (1) \geq \dots$ est décroissante : une répartition de $m$ jetons revient à choisir, dans chaque boîte, un début de la suite $δ_{i}$ , et le gain total est la somme des $m$ gains marginaux choisis. La somme maximum s'obtient en prenant les $m$ plus grands gains marginaux de toutes les boîtes (dans la limite de $Q$ par boîte), et comme chaque suite est décroissante, ces $m$ plus grands forment bien un début de chaque suite. C'est exactement ce que fait le glouton.
Boîte $0$ : $g_{0} = (0, 0, 10)$ (non concave : le second jeton rapporte plus que le premier) ; boîte $1$ : $g_{1} = (0, 6, 7)$ ; $m = 2$ . Le glouton met le premier jeton dans la boîte $1$ (gain marginal $6$ contre $0$ ), puis le second encore dans la boîte $1$ ( $1$ contre $0$ ) : gain $7$ . Deux jetons dans la boîte $0$ rapportent $10$ .


concave : glouton 21, optimum 21
contre-exemple : glouton 7, optimum 10

Énoncé

Corrigé