Objectifs

1. Comprendre le concept de la programmation dynamique ;
2. Mettre en place une solution dynamique ;
3. Évaluer la complexité algorithmique.

TP

Les questions se répondent sur papier.
Le TP se fait sur python.

TP3 - Le problème des découpes de planches

Contexte

La scierie Borges Jaumont dans les Vosges cherche à optimiser le prix de vente de ses planches.
À partir d'une planche donnée, l'entreprise peut la couper en plus petites planches de longueur définie, dont le prix est indiqué dans le tableau ci-dessous :

Longueur	0	1	2	3	4	5	6	7	8	9	10
Prix	0	1	5	8	9	10	17	17	20	24	30

On va chercher à maximiser le prix de vente d'une planche.

Compréhension

Dans un premier temps, on souhaite déterminer le prix maximal que l'on pourrait obtenir avec une planche de longueur 4.

1. Sous la forme d'un arbre, énumérer toutes les possibilités de découpe d'une planche de longueur 4.
2. Pour chaque découpe possible, indiquer le prix obtenu.
3. Déterminer la découpe la plus rentable, avec son prix.

Approche naïve

L'informaticien de l'entreprise cherche à créer un programme permettant d'étudier toutes les possibilités de découpe, et retournant le prix maximal obtenu. Il a besoin d'aide.

4. Créer la liste des prix p, contenant, pour chaque indice, le prix correspondant à la longueur d'une planche.
5. Que représente p[i] ?
6. La fonction doit être récursive. Quel est le cas d'arrêt ?
7. Si on coupe une planche de longueur n en i et n-i, comment exprimer le problème sous forme de sous-problèmes ?
8. Écrire la fonction récursive coupe(n,p) ayant pour paramètres n représentant la longueur de la planche, et p la liste des prix pour chaque longueur de planche.

Petite aide

9. Un employé a souhaité exécuter cette fonction avec une planche de taille 11, et a obtenu cette erreur : ”IndexError: list index out of range”. D'où provient l'erreur dans ce programme, et pourquoi apparait-elle ?
10. Corriger le problème.
11. Le bug corrigé, ce même employé tente de calculer le prix maximal d'une planche de longueur 30. Le programme a mis 1h à donner une solution. Expliquer pourquoi.

Approche dynamique

L'informaticien tente d'améliorer son programme et veut utiliser la programmation dynamique. Il a besoin d'aide pour son programme.

12. Proposer une solution consistant à utiliser une mémoire pour obtenir le prix optimal de la découpe d'une planche.

L'informaticien propose une solution mais le fichier est corrompu :

def planche_memo(n: int, p: list) -> int:
    """
    Crée la mémoire et retourne le prix d'une planche de longueur n.
    """
    mem = ...  # Initialisation de la mémoire avec 0 (valeur non calculée)
    return coupe_dyna(..., ..., ...)

def coupe_dyna(n: int, p: list, mem: list) -> int:
    """
    Fonction dynamique récupérant la valeur dans la mémoire si elle existe, 
    ou bien la calcule en fonction des valeurs précédemment calculées 
    et l'ajoute dans la mémoire.

    @return : le meilleur prix possible pour une planche de longueur n.
    """
    if n == 0:
        return ...

    elif ... != ... :  # Si la valeur est déjà calculée, on la retourne
        return ...
    else :
        resultat = ...  # On cherche le maximum des découpes possibles
        for i in range(..., ...):
            if ... < ...:  # Vérifier que i est bien dans les indices de p
                resultat = max(..., ...)

        mem[n] = ...  # Stocker le résultat dans la mémoire
        return ...

13. Recopier et compléter le programme pour qu'il puisse utiliser les valeurs mémoïsées afin de calculer la valeur optimale d'une coupe de taille n.