TP2 - Le problème du sac à dos

Objectifs

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

Le TP se fait sur python.

Introduction

Salut à toi, jeune aventurier ! Te voilà dans un univers de type RPG, où ton objectif est... de survivre, le plus longtemps possible.
Pour survivre, tu vas avoir besoin d'objets.

Mais, comme dans tout univers RPG, tu es soumis à des règles de physique élémentaire... Tu ne peux porter sur toi que ce que ton corps peut supporter.
Autrement dit : chaque ressources, objets, possèdent un poids, et tu es soumis à une limite de poids.

Voyons voir si tu as compris ce que j'ai dit.

Tu ne peux porter que 15 kilos, et voici une liste d'objets s'offrant miraculeusement à toi (il faut bien débuter) :

Objet	Casque en bois	Épée en bois	Veste en paille	Botte en bois	Armure en bois
Poids	5	10	2	3	5

Tu ne peux prendre qu'un seul objet de chaque. Quel combinaison d'objets te permettrait d'en prendre le maximum ?

Se faire de l'argent 💰

Tout au long de ton aventure, tu seras amené à améliorer ton équipement. Tu pourras en trouver, certains pourront également s'acheter.
Tu l'auras compris, pour pouvoir devenir le plus grand des aventuriers, il va falloir se faire un max de blé (le code de triche chatgpt ne fonctionne pas).

Pour commencer, je te donne ce sac un peu maigrichon, te permettant de porter jusqu'à 10 kilos.

En te baladant dans la ville de Fortdhiver (nom donné au hasard, aucunement en référence au fait qu'on soit dans une montagne), tu trouves un coffre (abandonné, normalement) renfermant les objets suivants, en un seul exemplaire :

Objet	Poids	Valeur
Médaille	2	2
Livre ancien	1	5
Bague en diamant	2	6
Boussole	3	4
Dague	7	8
Lingot d'acier	5	7

Sachant que tu ne peux pas dépasser le poids maximal de ton sac, quels objets prendrais-tu, pour maximiser la valeur totale ?

Pour t'aider à choisir les objets les plus rentables, un inconnu te propose un mystérieux artefact (que l'on appellera ordinateur), te permettant, en lui donnant les bonnes instructions, de déterminer automatiquement les objets les plus rentables à prendre, si tu trouves un nouveau coffre.

Pour commencer, il faut matérialiser les objets du coffre sur l'ordinateur.

Les objets du coffre sont définis par un nom, un poids et une valeur. Tu dois créer une classe Objet avec ces propriétés.
Crée maintenant l'ensemble des objets présents dans le coffre, et ajoute-les dans une liste.

Première approche

L'une des solutions pour résoudre le problème serait de prendre les objets avec les plus grosses valeurs en premier.

Écris une fonction tri_valeur(liste_objet) qui prend en paramètre une liste d'objets, et retourne la même liste d'objets mais triée par ordre décroissant des valeurs (l'objet avec la valeur la plus grande est le premier élément).
Écris une fonction sac_glouton(liste_objet, poids) qui prend en paramètre une liste d'objet triée et un entier correspondant à la capacité du sac, et qui retourne les objets ayant la plus grosse valeur que l'on peut prendre sans dépasser la capacité du sac.

Un grand sage (chauve et barbu) t'avait expliqué par le passé que ce n'était pas la meilleure des solutions, car tu ne ferais pas les choix optimaux. Il t'avait dit qu'il faut étudier tous les choix possibles pour trouver la meilleure solution.

N'ayant évidemment pas enregistré toutes les informations qu'il t'a donné, il t'a donné un vieux parchemin sur lequel il est écrit ceci :

def sac_arbre(liste_objet, poids, taille_liste=0):
   # Cas de base : plus d'objets ou plus de capacité
    if ... or ...:
        return [], 0  # Aucune valeur ajoutée

    # Je ne choisis pas l'objet, je passe au suivant
    sans_objet, valeur_sans = sac_arbre(..., ..., ...)

    # Je choisis l'objet
    objet_choisi = liste_objet[...]

    # Mais il est trop lourd
    if ... > ...:
        return sans_objet, valeur_sans  

    #Il n'est pas trop lourd, je le prends et recommence avec l'objet d'après
    avec_objet, valeur_avec = sac_arbre(..., ..., ...)
    #J'augmente la valeur totale avec celle de l'objet choisi
    valeur_avec += ...

    #Je choisis la valeur la plus avantageuse parmi les 2 que j'ai calculé
     if ... > ...:
        #Celle avec l'objet pris est avantageuse, je retourne l'objet choisi avec la liste des objets choisis (et la valeur)
        return [...] + ..., ...
    else:
        #Celle sans l'objet est plus avantageuse, je retourne la liste des objets obtenues sans l'objet choisi, et la valeur sans
        return ..., ...

Il manque des informations sur le parchemin. À toi de le compléter !

Maintenant que tu as trouvé toutes les solutions possibles, tu remarqueras qu'elle n'est pas très bonne car tu recalcules plusieurs fois les mêmes sous-solutions. Pour gagner (littéralement) en expérience, il va falloir améliorer ce programme et mémoïser les informations.

Avant de programmer, il faut bien en saisir le fonctionnement. Pour comprendre le fonctionnement de la mémoïsation, on se propose d'étudier le tableau suivant :

Taille du sac/Objet	0	1	2	3	4	5	6	7	8	9	10
Dague
Lingot d'acier
Bague en diamant
Livre ancien
Boussole
Médaille

Ce tableau se construit ligne par ligne, puis colonne par colonne. On va compléter dans un premier temps, la valeur maximale que tu auras dans ton sac en n'ayant qu'une dague comme objet. On peut ainsi obtenir le tableau suivant :

Taille/Objet	0	1	2	3	4	5	6	7	8	9	10
Dague	0	0	0	0	0	0	0	8	8	8	8
Lingot d'acier
Bague en diamant
Livre ancien
Boussole
Médaille

Maintenant, si on rajoute le lingot d'acier (toujours en cherchant à maximiser la valeur), on obtient ce tableau :

Taille/Objet	0	1	2	3	4	5	6	7	8	9	10
Dague	0	0	0	0	0	0	0	8	8	8	8
Lingot d'acier	0	0	0	0	0	7	7	8	8	8	8
Bague en diamant
Livre ancien
Boussole
Médaille

Pour une taille de 5 et 6kg, il est plus optimal de prendre le lingot d'acier. Par contre, si on passe à 8kg, il devient plus optimal de prendre la dague.
Dans la colonne 7 du lingot d'acier, le programme doit prendre la valeur maximale entre :

La valeur qu'il a trouvé sur la ligne du dessus ;
La valeur qu'il a trouvé sur la même ligne au poids précédent ;
La somme de l'objet avec la valeur trouvée sur la ligne précédente, à la colonne de la taille du sac moins celle de l'objet en question. Dans ce cas, cela donnerait le maximum entre :
8 (case du dessus, [0][7]) ;
7 (case à gauche, [1][6]) ;
7 (somme de la valeur du lingot avec la case [0][2]).

La valeur maximale se situera ainsi dans la case tout en bas à droite.

Pour connaître la valeur maximale sans avoir à calculer toutes les possibilités, complète le tableau.
Pour programmer cette solution, il va falloir que tu crées une fonction sacADos(liste_objet, poids) dont le but va être de créer la mémoire (le tableau), rempli pour chaque case d'une liste contenant [],0 (liste des objets et valeur). Elle appellera par la suite la fonction que tu as complété précédemment, modifiée.
Reprend la fonction sac_arbre créée précédemment, et modifie-la pour qu'elle prenne en compte la mémoire.
Pour tester la différence (on ne la verra pas en terme de temps sur un poids léger ainsi que peu d'objets), tu vas faire un compteur d'appels de la fonction (à l'aide de variables globales).