Séance pratique

Durée2h30

Présentation et objectifs

Important

L’objectif de cette séance est de vous aider à maîtriser des notions importantes en informatique. Un assistant de programmation intelligent tel que GitHub Copilot, que vous avez peut-être déjà installé, sera capable de vous fournir une solution à ces exercices en se basant uniquement sur un nom de fichier judicieusement choisi.

Dans un objectif de formation, nous vous conseillons de désactiver ces outils dans un premier temps.

À la fin de l’activité pratique, nous vous suggérons de reprendre l’exercice avec ces outils activés. Suivre ces deux étapes améliorera vos compétences tant fondamentales que pratiques.

L’implémentation des solutions n’est pas indispensable, privilégiez le travail collaboratif sur papier.

Contenu de l’activité

1 — Le problème du sac à dos

Le problème est le suivant (cité de Comer et al.).

Un voleur qui cambriole un magasin veut emporter la charge la plus précieuse qui peut être transportée dans un sac à dos capable de porter au maximum $W$ livres de butin. Le voleur peut choisir de prendre n’importe quel sous-ensemble de $n$ objets dans le magasin. Le $i$ème objet vaut $v_i$ dollars et pèse $w_i$ livres, où $v_i$ et $w_i$ sont des entiers. Quels objets le voleur devrait-il prendre ?

Remarque : Le problème est appelé le problème du sac à dos 0-1 parce que le voleur peut soit prendre un objet soit le laisser, mais ne peut pas prendre une fraction d’un objet.

Pour cet exercice, nous allons créer un fichier knapsack.py et implémenter diverses solutions au problème du sac à dos 0-1. En parallèle, nous allons créer un fichier test_knapsack.py pour tester les fonctions implémentées dans knapsack.py. Nous ne vérifierons pas seulement la justesse des fonctions mais aussi leur efficacité.

Comme paramètres de base, nous considérerons les valeurs suivantes :

  • Le poids maximum que le sac à dos peut porter : $W = 50$.
  • La liste des poids des objets : $weights = [10, 20, 30]$.
  • La liste des valeurs des objets : $values = [60, 100, 120]$.

Deux ensembles de paramètres supplémentaires seront considérés pour les tests :

  • $W = 15$, $weights = [12, 7, 11, 8, 9]$, $values = [24, 13, 23, 15, 16]$.
  • $W = 30$, $weights = [2, 3, 5, 7, 1, 4, 6, 8, 10, 9, 2, 3, 5, 7, 1]$, $values = [10, 15, 7, 8, 4, 12, 6, 11, 20, 18, 5, 9, 14, 16, 3]$.

Le premier ensemble de paramètres est suffisamment petit pour vous permettre de calculer les résultats à la main. Les deux autres ensembles de paramètres sont plus grands et nécessiteront l’implémentation d’algorithmes efficaces et vous permettront de ressentir la complexité de chaque approche.

1.1 — Solution à la main

Oubliez le programme, prenez un stylo et du papier et considérez le premier exemple de test. Listez toutes les combinaisons possibles d’objets qui peuvent être pris, et pour chacune d’elles, calculez le poids total et la valeur totale. Ensuite, déterminez la combinaison qui maximise la valeur totale sans dépasser le poids maximum que le sac à dos peut porter. Cette solution vous aidera à comprendre le problème et les résultats attendus.

1.2 — Une solution récursive

La première fonction à implémenter est une solution récursive au problème du sac à dos 0-1. La fonction doit avoir la signature suivante :

def knapsack_recursive(W: int, weights: List[int], values: List[int]) -> int:
    """ Recursive solution to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    pass

La solution récursive est simplement basée sur la propriété de sous-structure optimale du problème : si la charge la plus précieuse inclut l’objet $i$, alors la charge restante doit être la charge la plus précieuse pesant au maximum $W - w_i$ que le voleur peut prendre parmi les objets originaux, en excluant l’objet $i$._

Indices

Utilisez une fonction récursive auxiliaire qui inclut un paramètre supplémentaire $n$ indiquant l’objet actuel à vérifier. Le cas de base de la récursivité est qu’il n’y a plus d’objets à étudier ou plus d’espace dans le sac à dos. Les appels récursifs correspondent au cas où l’objet actuel est trop lourd pour être ajouté au sac à dos et aux cas où l’objet est pris ou non. La meilleure solution de ces deux dernières possibilités doit être retournée.

1.3 — Une solution récursive avec mémoïsation

Une deuxième étape consiste à implémenter une solution récursive avec mémoïsation. La fonction doit avoir la signature suivante :

def knapsack_recursive_memo(W: int, weights: List[int], values: List[int]) -> int:
    """ Recursive solution with memoization to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    pass

La solution récursive avec mémoïsation consiste à stocker les résultats des sous-problèmes dans une table pour éviter de les recalculer.

1.4 — Une solution de programmation dynamique

Une troisième étape consiste à implémenter une solution de programmation dynamique au problème du sac à dos 0-1. La fonction doit avoir la signature suivante :

def knapsack_dp(W: int, weights: List[int], values: List[int], n: int) -> int:
    """ Dynamic programming solution to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
            - n: the number of items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    pass

Contrairement à la solution de mémoïsation, la solution de programmation dynamique remplit la table de manière ascendante.

Indices

Pour implémenter la solution de programmation dynamique, suivez ces étapes :

  1. Initialiser la table : Créez une matrice de dimensions (n+1) x (W+1)n est le nombre d’éléments et W est le poids maximum que le sac à dos peut porter. Initialisez toutes les valeurs à 0.

  2. Remplir la table : Itérez à travers chaque élément et chaque capacité de poids, en remplissant la table selon les conditions suivantes :

    • Si le poids de l’élément actuel est supérieur à la capacité actuelle, la valeur est la même que la valeur sans inclure l’élément actuel.
    • Sinon, la valeur est le maximum entre inclure l’élément actuel ou ne pas l’inclure.
  3. Retourner le résultat : La valeur à table[n][W] sera la valeur maximale qui peut être portée dans le sac à dos.

1.5 — Une solution gloutonne

La dernière étape consiste à implémenter une solution gloutonne au problème du sac à dos 0-1. La fonction doit avoir la signature suivante :

def knapsack_greedy(W: int, weights: List[int], values: List[int]) -> int:
    """ Greedy solution to the 0-1 knapsack problem.
        In: 
            - W: the maximum weight the knapsack can carry
            - weights: the list of weights of the items
            - values: the list of values of the items
        Out:
            - the maximum value that can be carried in the knapsack
    """
    pass

La solution gloutonne consiste à sélectionner l’élément avec le ratio valeur-poids maximum jusqu’à ce que le sac à dos soit plein.

Questions :

  1. Que pouvez-vous dire de la solution gloutonne comparée aux autres solutions ?

2 — Optimisez vos solutions

Ce que vous pouvez faire maintenant, c’est utiliser des outils d’IA tels que GitHub Copilot ou ChatGPT, soit pour générer la solution, soit pour améliorer la première solution que vous avez proposée ! Essayez de le faire pour tous les exercices ci-dessus, pour voir les différences avec vos solutions.

Pour aller plus loin

3 — Le problème du sac à dos fractionnaire

Considérez désormais que vous pouvez prendre une fraction de chaque objet et pas nécessairement sont entièreté.

Quelle serait la solution gloutonne à cette variante du problème ? Quelle est la complexité de cette solution gloutonne et que peut-on dire du résultat obtenu ?

Pour aller au-delà

Vous venez donc de voir plusieurs types de solutions algorithmiques :

  • diviser pour régner
  • programmation dynamique
  • gloutonne

Il existe d’autres familles d’algorithmes. Nous étudierons les approches basées sur l’intelligence artificielle lors de la prochaine session, mais vous pouvez désormais vous intéresser aux méthodes dites :

  • Monte Carlo
  • Las Vegas
  • Backtracking
  • Satisfaction de contraintes
  • Programmation linéaire

En vous documentant sur ces méthodes, trouvez un problème approprié pour chacune d’elles.