On souhaite ranger différents objets dont les poids sont connus dans des boîtes toutes identiques et dont la capacité ne peut pas dépasser une certaine valeur.
Les poids sont des nombres entiers strictement positifs. Il sont fournis dans une liste triée dans l'ordre décroissant.
On garantit que la capacité maximale des boîtes est supérieure ou égale au poids de l'objet le plus lourd.
Le but de cet exercice est de construire un « rangement valide » en suivant un méthode imposée décrite plus bas. Un « rangement valide » est une liste Python dans laquelle :
chaque élément est une liste contenant le poids de certains objets,
le poids de chaque objet apparaît une unique fois dans la liste,
le poids total de chaque sous-liste est inférieur ou égal à la contenance maximale des boîtes.
Rangements (in)valides
🐍 Script Python
poids_objets=[7,4,3,1]poids_max=8
Dans cet exemple, on a quatre objets à ranger (de poids 7, 4, 3 et 1) et le poids maximal des boîtes vaut 8 (inclus).
La liste [[7,1],[4,3]] est un rangement valide utilisant deux boîtes. On a placé les objets de poids 7 et 1 dans une boîte et les deux autres dans une seconde boîte. Le poids total de chaque boîte ne dépasse par 8.
La liste [[7],[4,3,1]] est aussi un rangement valide. Elle utilise aussi deux boîtes.
La liste [[7],[4],[3],[1]] est aussi un rangement valide. Elle utilise quatre boîtes.
Par contre, la liste [[7,4],[3,1]] n'est pas un rangement valide : le poids total de la première boîte est strictement supérieur au poids maximal d'une boîte.
Pour ranger les objets, on impose la méthode suivante :
on crée deux listes vides boites et poids_boites destinées à contenir les listes représentant les boîtes et leurs poids respectifs ;
on parcourt dans l'ordre initial la liste des poids des objets et on place chacun d'entre eux dans la première sous-liste de boites pouvant le contenir ;
si aucune boîte ne peut le contenir, on le place dans une nouvelle liste, elle-même placée à la fin de la liste boites.
Cette méthode permet d'obtenir, dans certains cas, un rangement utilisant un minimum de boîtes.
Déroulé
On applique l'algorithme dans le cas suivant :
🐍 Script Python
poids_objets=[7,4,3,1]poids_max=8
Les deux listes sont vides :
boites=[]
poids_boites=[]
On ajoute une nouvelle boîte pour cet objet :
boites=[[7]]
poids_boites=[7]
Cet objet ne peut pas aller dans la première boîte : on le place dans une nouvelle boîte.
boites=[[7],[4]]
poids_boites=[7,4]
Cet objet ne tient pas dans la première boîte mais tient dans la seconde :
boites=[[7],[4,3]]
poids_boites=[7,7]
Cet objet tient dans la première boîte :
boites=[[7,1],[4,3]]
poids_boites=[8,7]
Écrire la fonction rangement qui prend en paramètres la liste des poids des objets, poids_objets, ainsi que le poids maximal que peut recevoir une boîte, poids_max, et renvoie la liste des boîtes utilisées en appliquant la méthode décrite.
Ni la liste des boîtes, ni chacune de ses sous-listes ne seront triées.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)