Problème d'installation des étagères
Problème ! Etant donné la longueur du mur L et des étagères de deux longueurs m et n, trouvez le nombre de chaque type d'étagère à utiliser et l'espace disponible restant dans la solution optimale, de sorte que l'espace vide soit minimal. La plus grande des deux étagères est moins chère, c'est donc préférable. Cependant, le coût est secondaire et la première priorité est de minimiser l'espace vide sur le mur.
Exemple :
L = 7 m = 3 n = 5
2 0 1 (Nous utilisons deux unités de type m et il reste 1 place.)
L = 29 m = 3 n = 9
0 3 2 (0 * 3 + 3 * 9 = 27 ; 29 - 27 = 2 )
2 0 1 (Nous utilisons deux unités de type m et il reste 1 place.)
L = 29 m = 3 n = 9
0 3 2 (0 * 3 + 3 * 9 = 27 ; 29 - 27 = 2 )
Une approche simple et efficace consistera à essayer toutes les combinaisons possibles d'étagères qui s'insèrent dans la longueur du mur.
Pour mettre en œuvre cette approche avec la contrainte que les plus grandes étagères coûtent moins cher que la plus petite, à partir de 0, nous n'augmentons pas les étagères de type plus grand jusqu'à ce qu'elles puissent être ajustées. Pour chaque cas, nous calculons l'espace vide et stockons finalement cette valeur qui minimise l'espace vide. si l’espace vide est identique dans les deux cas, nous préférons celui qui n’a plus aucun des plus grands étagères.
def ProbEtageres(L, m, n):
nb_m = L/m
nb_n = 0
reste = L % m
# p et q sont des nombres d'étagères de longeur m,n respectivement.
# r est la longueur de mur restante
p = 0
q = 0
r = 0
while (L >= n):
q += 1
L -= n
p = L / m
r = L % m
if (r <= reste):
nb_m = p
nb_n = q
reste = r
return(nb_m, nb_n, reste)
# Tester la fonction
L = 7
m = 3
n = 5
nb_m, nb_n, reste = ProbEtageres(L, m, n)
print(str(int(nb_m)) + " " + str(nb_n) + " " + str(reste))2 0 1
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa
