On considère le problème suivant :
on a différents objets de poids divers que l’on veut ranger dans un certain nombre de contenants ayant une capacité limitée.
Par exemple, on a 8 objets de poids respectifs 7,6,3,4,8,5,9,2 que l’on veut ranger dans des cartons dont la capacité est de 11 kg maximum.
On veut évidemment, si possible :
– ranger tous les objets,
– minimiser le nombre de cartons nécessaires.
Exercice 1
Proposer différents algorithmes en langage « naturel ».
Pour chaque algorithme, déterminer l’invariant, le variant et préciser si la condition d’arrêt est vérifiée.
Tester vos algorithmes avec les 3 exemples.
Vos algorithmes permettent-ils d’obtenir une solution optimale ?
Exercice 2
Implémenter en Python vos différents algorithmes.
On utilisera des listes pour simuler les poids des objets et le rangement obtenu par l’algorithme.
Par exemple :
>>> poids=[6,5,5,3,3,2]
>>> rangement1_poids(12,3) # fonction avec un paramètre poids maximal et le nombre de carton
[[6,5],[5,3,2],[3]]correspondra à la solution :
Trouver la solution optimale à l’exemple 3.
Proposition de correction
Une proposition de correction avec 3 algorithmes :
– une algorithme de rangement totalement aléatoire : on tire un poids au hasard que l’on range dans une boîte disponible au hasard,
– un algorithme de rangement ordonné : on prend les poids au fur et à mesure et on les range dans la 1ere boîte disponible,
– un algorithme glouton sur le principe de « on range d’abord les poids les plus lourds dans la première boîte disponible ».
from random import randint
def creation_boites(nombre,poids_max):
'''
creation d'une liste de longueur n+1,
les n premiers éléments représentent une boite
le dernier élément représente la val max par boite
retour : une liste
>>> boites=creation_boites(6,12)
>>> boites==[[], [], [], [], [], [], 12]
True
'''
boites=[[] for i in range(nombre)]
boites.append(poids_max)
return boites
def boite_dispo(indice,val):
'''
indique si la boite correspondante à l'indice peut accueillir la val
sans dépasser le poids max
>>> boites=[[5,2], [9], [], [], [], [], 12]
>>> boite_dispo(0,5)
True
>>> boite_dispo(1,5)
False
>>> boite_dispo(10,5)
False
'''
global boites
if indice>=len(boites):
return False
if sum(boites[indice])+val>boites[-1]:
return False
return True
def indice_boite_aleatoire(val):
'''
détermine l'indice d'une boîte aléatoire pouvant
accueiller la valeur val, revoie False si aucune boîtes
n'est dispo
return : int ou False
'''
global boites
boites_dispo=[]
poids_max=boites[-1]
for i in range(len(boites)-1):
if boite_dispo(i,val)!=False:
boites_dispo.append(i)
if len(boites_dispo)==0:
return False
else :
indice_alea=randint(0,len(boites_dispo)-1)
return int(boites_dispo[indice_alea])
def algo_on_range_au_hasard(a_ranger):
'''
principe : on prend une valeur à ranger au hasard,
on la range au hasard dans un boite disponible si
il y en a une
return : False si on ne peut pas ranger une valeur,
sinon la liste boites avec les valeurs rangées aléatoriement
effet de bord : modifie la liste boites
'''
global boites
val_a_ranger=a_ranger.copy()
while len(val_a_ranger)>0 :
# on tire une valeur à ranger au hasard
val=val_a_ranger[randint(0,len(val_a_ranger)-1)]
# on cherche à la ranger aléatoirement
ind_alea=indice_boite_aleatoire(val)
# on teste si l'indice est un entier
# ind_alea!=False ne fonctionne pas pour
# ind_alea=0 ( False = 0 )
if type(ind_alea)==int:
boites[ind_alea].append(val)
else:
print("Je n'ai pas pu ranger tous vos éléments.")
return False
# on supprime la valeur rangée de la liste
# des valeurs à ranger
val_a_ranger.remove(val)
return boites
def algo_on_range_les_poids_successivement(a_ranger):
'''
principe : on prend les valeurs à ranger dans l'ordre au fur
et à mesure, on les range dans la 1ere boite disponible
return : False si on ne peut pas ranger une valeur,
sinon la liste boites avec les valeurs rangées
effet de bord : modifie la liste boites
>>> a_ranger=[11,12,8,1,5,4,3,7]
>>> boites=[[], [], [], [], [], 13]
>>> algo_on_range_les_poids_successivement(a_ranger)
>>> boites==[[11, 1], [12], [8, 5], [4, 3], [7], 13]
True
'''
global boites
for i in range(len(a_ranger)):
indice=0
while boite_dispo(indice,a_ranger[i])==False:
indice+=1
if indice==len(boites)-1:
print("Je n'ai pas pu ranger vos valeurs")
return False
boites[indice].append(a_ranger[i])
return boites
def rangement_par_poids_max(a_ranger):
'''
principe : on prend les valeurs à ranger par ordre décroissant au fur
et à mesure, on les range dans la 1ere boite disponible
return : False si on ne peut pas ranger une valeur,
sinon la liste boites avec les valeurs rangées
effet de bord : modifie la liste boites
>>> a_ranger=[11,12,8,1,5,4,3,7]
>>> boites=[[], [], [], [], [], 13]
>>> algo_on_range_les_poids_successivement(a_ranger)
>>> boites==[[12,1], [11], [8,5], [7,4], [3], 13]
True
'''
global boites
a_ranger.sort()
a_ranger.reverse()
for i in range(len(a_ranger)):
indice=0
while boite_dispo(indice,a_ranger[i])==False:
indice+=1
if indice==len(boites)-1:
print("Je n'ai pas pu ranger vos valeurs")
return False
boites[indice].append(a_ranger[i])
return boites
a_ranger=[11,12,8,1,5,4,3,7]
boites=creation_boites(5,13)
print("Algo aléatoire")
print("A ranger",a_ranger)
print("dans",boites)
algo_on_range_au_hasard(a_ranger)
print(boites)
print("Algo par parcours des listes")
boites=creation_boites(5,13)
print("A ranger",a_ranger)
print("dans",boites)
algo_on_range_les_poids_successivement(a_ranger)
print(boites)
print("Algo par parcours des listes")
boites=creation_boites(5,13)
print("A ranger",a_ranger)
print("dans",boites)
rangement_par_poids_max(a_ranger)
print(boites)