def generer_densite(taille, prix):
rapport = []
for i in range(1,len(taille)):
r = (taille[i], prix[i], prix[i]/ taille[i])
rapport.append(r)
return rapport
def decoupe_gloutonne(l:int, prix:list, taille:list) -> tuple :
rapport = generer_densite(taille, prix)
donnees = sorted(rapport, key=lambda donnee: donnee[2], reverse=True)
decoupe = {} # Couples (segment : nbre)
somme = 0
i = 0
while i < len(donnees) and l != 0:
segment = donnees[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[i][1]
i += 1
return (somme, decoupe)
def decoupe_brute_force(l:int, prix:list, taille:list) -> int :
if l == 0 :
return 0
valeur_max = 0
for i in range(1,len(taille)):
if l - taille[i] >= 0:
new_valeur = prix[i] + decoupe_brute_force(l-taille[i], prix, taille)
if new_valeur > valeur_max:
valeur_max = new_valeur
return valeur_max
def decoupe_dyn_descendante(l:int, prix:list, taille:list) :
return memoisation(l, prix, taille, {0:0})
def memoisation (l:int, prix:list, taille:list, dico) -> int:
if l not in dico:
valeur_max = 0
for i in range(1,len(taille)):
if l - taille[i] >= 0:
new_valeur = prix[i] + memoisation(l-taille[i], prix, taille, dico)
if new_valeur > valeur_max:
valeur_max = new_valeur
dico[l] = valeur_max
return dico[l]
def decoupe_dyn_ascendante(l:int, prix:list, taille:list) :
valeurs = [0 for i in range(l + 1)]
for long in range(l + 1):
if long == 0:
valeurs[long] = 0
else:
for i in range(0,len(taille)):
if long - taille[i] >= 0:
valeur = prix[i] + valeurs[long - taille[i]]
if valeur > valeurs[long]:
valeurs[long] = valeur
return valeurs[l]