Correction : programmation dynamique

Optimisation de la découpe de planches

RésolutionS du problème

1. Dans l'arbre ci dessous, on retrouve sur chaque nœud la taille de la planche qu'il reste à découper et sur chaque lien la taille de la découpe. Si l'on prend la branche de gauche, en partant de la racine, on réalise tout d'abord une découpe de 1, il reste ensuite une planche de 3 à découper.

2. 

3. La découpe optimale d'une planche de 4 est donc "2-2" avec un gain de 10€.

Solution récursive

1. La longueur de la planche restante sera l-i.
2. Le revenu total dans ce cas sera : p[i] + coupe_recurs(l-i, p)
3. Il faut choisir le maximum entre la découpe optimale d'une précédente hypothèse et la réponse à la question 2 :

   
   	fonction coupe_recurs(l, p):
   	    si l = 0:
   	        renvoyer l
   	    optim ← 0 ( ou optim = p[l] = le revenu minimal que l'on peut avoir avec cette longueur...)
   	    pour i de 1 à l:
   	        revenu ← p[i] + coupe_recurs(l-i, p)
   	        si revenu > optim:
   	            optim ← revenu
   	    renvoyer optim
   				

Implémentation :

def coupe_recurs(l: int, p: list)->int:
    if l == 0:
        return l
    
    optim = 0  # ou optim = p[l]
    for i in range(1, l+1):
        revenu = p[i]+coupe_recurs(l-i, p)
        if revenu > optim:
            optim = revenu
            
    return optim	
    
print(coupe_recurs(9, p)					
    	

Solutions dynamiques

1. On retrouve dans cet arbre, deux fois la découpe d'une planche de longueur 2 :

   

2. Cette arbre a une taille de 16.
3. De façon plus générale, pour une planche de longueur n, l'arbre aura une taille de n²

Du haut vers le bas ou Top-Bottom

def coupe_dyna_TB(l, p, r):
    if r[l] != None:
        return r[l]
    
    if l == 0:
        r[l] = 0
    else:
        for i in range(1, l+1):
            revenu = p[i]+coupe_dyna_TB(l-i, p, r)
            if revenu > r[l]:
                r[l] = revenu
    return r[l]	

l = 9
r = [None]*(l+1) # tableau à passer au premier appel de la fonction			
		

Du bas vers le haut ou Bottom-Up

Le remplissage du tableau r des résultats successifs, de taille l+1, se fait en partant de l'indice 0; par exemple, pour l = 4 :

• r[0] = p[0] = 0
• r[1] = p[1]+r[0] = 1
• r[2] = max(p[2]+r[0], p[1]+r[1]) = max(5, 1+1) = 5
• r[3] = max(p[3]+r[0], p[1]+r[2], p[2]+r[1]) = max(8, 1+5, 5+1) = 8
• r[4] = max(p[4]+r[0], p[1]+r[3], p[2]+r[2], p[3]+r[1]) = max(8, 1+8, 5+5, 8+1) = 10

Donc, pour une planche de longueur i, le revenu optimal sera : r[i] = max(p[j]+r[i-j]), pour toutes les valeurs de j de 0 à i.

Le tableau r contiendra alors tous les revenus optimaux pour chaque longueur i, mais seul le dernier nous intérèsse...

def dyna_coupe_BU(l, p):
    r = [0 for i in range(l+1)]
    
    for i in range (1, l+1):
        r[i] = 0
        for j in range (0, i+1):
            revenu = p[j] + r[i-j]
            if revenu > r[i]:
                r[i] = revenu
    return r[n]