Découper une barre — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 3)

Découper une barre

Sacs avec répétitions, multi-ensembles et couples de sacs · niveau 2

Énoncé

Une scierie vend des barres de longueur $ℓ \in {1, \dots, 8}$ au prix $prix (ℓ)$ :

$ℓ$	1	2	3	4	5	6	7	8
$prix (ℓ)$	1	5	8	9	10	17	17	20

Elle dispose d'une barre de longueur $L$ qu'elle peut découper en morceaux de longueurs entières (sans perte).

Montrer qu'il s'agit d'un sac avec répétitions : quels sont les objets, leurs tailles, leurs valeurs ? Pourquoi peut-on ici supprimer l'indice $k$ ?
On note $r (ℓ)$ le prix maximum d'une barre de longueur $ℓ$ . Donner l'équation de récurrence, écrire le programme et donner une découpe optimale de la barre de longueur $8$ .

Corrigé

Les objets sont les longueurs de morceaux $ℓ = 1, \dots, 8$ (taille $ℓ$ , valeur $prix (ℓ)$ ), disponibles en nombre illimité ; la contenance est $L$ . Comme la barre est entièrement vendue et qu'un morceau de longueur $1$ existe toujours, on peut raisonner directement sur le dernier morceau sans numéroter les objets : c'est le même raisonnement que pour le rendu de monnaie.
Base : $r (0) = 0$ . Hérédité : $\forall ℓ \geq 1$ ,

$r (ℓ) = max {prix (i) + r (ℓ - i) : 1 \leq i \leq min (ℓ, 8)} .$


static int[] decoupe(int[] prix, int L) {
    int[] R = new int[L + 1];                       // base : R[0] = 0
    for (int l = 1; l < L + 1; l++)                 // l croissants
        for (int i = 1; i <= Math.min(l, prix.length); i++)
            R[l] = Math.max(R[l], prix[i-1] + R[l - i]);  // dernier morceau : i
    return R;
}


== decoupe : r = [0, 1, 5, 8, 10, 13, 17, 18, 22]
decoupe optimale de 8 : 6 2

La barre de longueur $8$ se vend au mieux $22$ : un morceau de $6$ ( $17$ ) et un morceau de $2$ ( $5$ ), mieux que la barre entière ( $20$ ).


nom : r
valeurs : 0 1 5 8 10 13 17 18 22
colorier : 8
vert : 0 6
fleches : 0->6:+17 6->8:+5
legende : r(8) = 5 + r(6) = 5 + 17 = 22 : morceaux de 6 et de 2

Complexité $Θ (8 L)$ .