proposition correction algo rangement
objets=[3,7,6,3,4,8,5,9,2,2]
carton_max=11
nbre_cartons=5
# avec boucles for
def rangement(objets):
'''
>>>rangement(objets)
[[3, 7], [6, 3, 2], [4, 5, 2], [8], [9]]
'''
cartons=[[] for i in range(nbre_cartons)]
for objet in objets:
ranger=False
for carton in cartons:
if ranger==False:
poids_carton=0
for obj in carton:
poids_carton+=obj
if poids_carton+objet<=carton_max:
carton.append(objet)
ranger=True
print(cartons)
return cartons
# avec boucles while
def rangement2(objs):
objets=objs.copy()
cartons=[[] for i in range(nbre_cartons)]
while objets!=[]:
objet=objets[0]
carton_dispo=False
i=0
while carton_dispo==False:
# on cherche un carton dispo
carton=cartons[i]
poids=0
for obj in carton:
poids+=obj
if poids+objet<=carton_max:
carton.append(objet)
objets.remove(objet)
carton_dispo=True
else:
i+=1
print(cartons)
return cartons
# correction algo du kp
poids_max=30
# objets valeur et poids
objets=[[70,13],[40,12],[30,8],[30,10]]
def calcul_densite(objets):
'''
>>>calcul_densite(objets)
[5.4,3.3,3.7,3]
'''
densite=[]
for obj in objets:
d=obj[0]/obj[1]
densite.append(round(d,1))
return densite
def classe_densite_decroissant(objets):
'''
>>>classe_densite_decroissant(objets)
[[70,13],[30,8],[40,12],[30,12]]
'''
objets_a_ranger=objets.copy()
densites=calcul_densite(objets)
objets_ranges=[]
# tant qu'il y a des objets à ranger
while len(objets_a_ranger)>0:
# je cherche l'indice du mx des densites
ind_max=densites.index(max(densites))
# j'ajoute l'objet correspondant aux objets ranges
objets_ranges.append(objets_a_ranger[ind_max])
# j'enleve la densite et l'objet de mes listes
del densites[ind_max]
del objets_a_ranger[ind_max]
return objets_ranges
def kp(objets):
'''
applique la methode du kp aux objets
>>>kp(objets)
[[70,13],[30,8]]
'''
sac_a_dos=[]
objets_classes=classe_densite_decroissant(objets)
poids_objets=0
indice_objet=0
while poids_objets <= poids_max:
obj=objets_classes[indice_objet]
sac_a_dos.append(obj)
indice_objet+=1
poids_objets+=obj[1]
return sac_a_dos