Un magasin achète des cordes d'escalade de longueur 
et les découpe (soigneusement) en cordes plus
petites pour les vendre à ses clients. On souhaite
déterminer un découpage optimal pour maximiser le revenu,
sachant que les prix de ventes 
d'une corde de
mètres sont donnés.
Par
exemple, supposons qu'on dispose d'une corde de 
mètres, avec les prix de ventes indiqués dans le tableau
suivant :
|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
0 | 1 | 5 | 8 | 9 | 10 | 17 | 18 | 20 | 24 | 26 |
Lorsqu'on met en œuvre une stratégie gloutonne, on cherche, à chaque étape, le meilleur choix « du moment », c'est à dire un choix optimum local.
comme étant le rapport 
, c'est-à-dire son prix au
mètre. Expliquer en quoi cette grandeur pourrait être
pertinente dans la mise en œuvre d'un algorithme glouton.
Puisqu'on cherche à maximiser le profit, l'idée est de commencer à découper la corde par les longueurs qui rapportent le plus à l'instant où l'on effectue la découpe, c'est à dire les segments dont la densité est la plus grande.
une corde de longueur peut être
découpée ?
La division entière : 
?
Le modulo : L % i
def decoupe_gloutonne(L, s, p):
"""
Détermine grâce à une stratégie gloutonne la découpe optimale
d une corde, connaissant les longueurs des segments possibles
et les valeurs associées.
Paramètres
----------
L : int
Longueur de la corde
s : list[int]
Liste des segments possibles
p : list[int]
Prix associés aux segments
Valeur retournée
----------------
(somme, {segment : nombre})
Tuple formé de la somme gagnée "optimale"
et du dictionnaire des segments de découpe accompagnés de leur nombre.
"""
Utiliser les deux instructions suivantes dans le corps de la fonction (se renseigner sur l'influence du paramètre key dans la définition de la fonction sorted) :
donnees = [(s[i], p[i], p[i] / s[i]) for i in range(1, len(s))] donnees = sorted(donnees, key=lambda donnee: donnee[2])
def decoupe_gloutonne(L, s, p):
"""
Détermine grâce à une stratégie gloutonne la découpe optimale
d une corde, connaissant les longueurs des segments possibles
et les valeurs associées.
Paramètres
----------
L : int
Longueur de la corde
s : list[int]
Liste des segments possibles
p : list[int]
Prix associés aux segments
Valeur retournée
----------------
(somme, {segment : nombre})
Tuple formé de la somme gagnée "optimale"
et du dictionnaire des segments de découpe
accompagnés de leur nombre.
"""
# Préparation des données en vue du tri sur la densité
donnees = [(s[i], p[i], p[i] / s[i]) for i in range(1, len(s))]
# Tri des données par densité croissante
donnees = sorted(donnees, key=lambda donnee: donnee[2])
# Valeurs retournées
decoupe = {} # Couples (segment : nbre)
somme = 0
i = 0
while i < len(donnees) and L != 0:
segment = donnees[-1 - i][0]
# Pas la peine de considérer les segments trop grands
if segment <= L:
# Nbre de segments
nbre = L // segment
# Longueur de corde restante
L = L % segment
# Ajout au dictionnaire résultat
decoupe[segment] = nbre
# Ajout à la somme totale
somme += nbre * donnees[-1 - i][1]
i += 1
return (somme, decoupe)
?
La stratégie gloutonne nous apprend que l'on peut gagner 9.
Remarque. À partir de cette section on ne cherche plus à connaître la découpe qui conduit à la somme maximale. On se contente de chercher cette somme.
la fonction qui donne la valeur
maximale que l'on peut obtenir en découpant une corde de
longueur . Indiquer la
relation de récurrence que vérifie la fonction .
où 
est l'un des segments possibles et
le prix associé.
La relation suppose que l'itération porte sur tous les segments possibles.
def decoupe_force_brute(longueur: int,
longueurs: List[int],
prix: List[int]) -> int:
"""
Détermine grâce à une stratégie par force brute la découpe optimale
d une corde, connaissant les longueurs des segments possibles
et les valeurs associées.
"""
def decoupe_force_brute(longueur: int,
longueurs: List[int],
prix: List[int]) -> int:
"""
Détermine grâce à une stratégie par force brute la découpe optimale
d une corde, connaissant les longueurs des segments possibles
et les valeurs associées.
"""
if longueur == 0:
return 0
valeur_max = 0
for (i, segment) in enumerate(longueurs):
if longueur - segment >= 0:
valeur_new = prix[i] + decoupe_force_brute(longueur - segment,
longueurs, prix)
if valeur_new > valeur_max:
valeur_max = valeur_new
return valeur_max
?
La stratégie par force brute nous apprend que l'on peut gagner 10.
La programmation dynamique est une technique dont le principe consiste à découper un problème en sous-problèmes (non indépendants les uns des autres), à les résoudre et à stocker les résultats de ces sous-problèmes dans un tableau afin de les réutiliser.
Il faut utiliser un dictionnaire afin de stocker les résultats des sous-problèmes rencontrés lors des apples récursifs.
def decoupe_memoisation(longueur: int, longueurs: List[int],
prix: List[int]) -> int:
"""
Détermine en utilisant la mémoïsation la découpe optimale
d une corde, connaissant les longueurs des segments possibles
et les valeurs associées.
Cette fonction est une fonction enveloppe.
"""
def decoupe_memoisation(longueur: int, longueurs: List[int],
prix: List[int]) -> int:
"""
Détermine en utilisant la mémoïsation la découpe optimale
d une corde, connaissant les longueurs des segments possibles
et les valeurs associées.
Cette fonction est une fonction enveloppe.
"""
memo = {0: 0}
def _memoisation(longueur: int, longueurs: List[int], prix: List[int],
memo: Dict[int, int]) -> int:
"""
Fonction qui effectue le traitement.
"""
if longueur not in memo:
valeur_max = 0
for (i, segment) in enumerate(longueurs):
if longueur - segment >= 0:
valeur_new = prix[i] + _memoisation(
longueur - segment, longueurs, prix, memo)
valeur_max = max(valeur_max, valeur_new)
memo[longueur] = valeur_max
return memo[longueur]
_memoisation(longueur, longueurs, prix, memo)
return memo[longueur]
La réponse doit être identique puisque la mémoïsation ne modifie pas fondamentalement l'algorithme mais enregistre simplement les calculs intermédiaires de façon à ne pas avoir à les calculer plusieurs fois.
La méthode tabulaire consiste à calculer tous les sous-problèmes en partant du plus petit jusqu'au problème recherché.
Il faut utiliser un tableau afin de stocker tous les calculs intermédiaires, en partant du plus petit sous-problème.
def decoupe_tabulaire(longueur: int, longueurs: List[int],
prix: List[int]) -> int:
"""
Détermine en utilisant la méthode tabulaire la découpe optimale
d une corde, connaissant les longueurs des segments possibles
et les valeurs associées.
"""
def decoupe_tabulaire(longueur: int, longueurs: List[int],
prix: List[int]) -> int:
"""
Détermine en utilisant la méthode tabulaire la découpe optimale
d une corde, connaissant les longueurs des segments possibles
et les valeurs associées.
"""
valeurs = [0 for i in range(longueur + 1)]
for long in range(longueur + 1):
if long == 0:
valeurs[long] = 0
else:
for i, segment in enumerate(longueurs):
if long - segment >= 0:
valeur = prix[i] + valeurs[long - (i + 1)]
if valeur > valeurs[long]:
valeurs[long] = valeur
return valeurs[longueur]
La réponse doit être identique puisque la méthode tabulaire ne modifie pas fondamentalement l'algorithme mais enregistre simplement les calculs intermédiaires de façon à ne pas avoir à les calculer plusieurs fois.
La correction se trouve à cette adresse.