Aller au contenu

Mise en boîte⚓︎

On n'utilisera pas sum dans cet exercice.

On souhaite ranger différents objets dont le poids est connu dans des boîtes dont la capacité totale ne peut pas dépasser une certaine valeur.

Les poids sont fournis dans une liste triée dans l'ordre décroissant. Il sont tous exprimés en kilogrammes.

Toutes les boîtes ont la même contenance maximale et l'on garantit que celle-ci est supérieure ou égale au poids de l'objet le plus lourd.

Exemple (1)
🐍 Script Python
poids_objets = [7, 5, 3, 1]
poids_max = 8

Dans cet exemple, on a quatre objets à ranger (de poids 7, 5, 3 et 1 kg) et les boîtes ne peuvent pas peser plus de 8 kg (inclus).

On appelle « rangement valide » la donnée d'une liste Python dans laquelle chaque élément est une liste contenant les poids de certains objets :

  • chaque poids doit apparaître une unique fois dans la liste,
  • le poids total de chaque sous-liste doit être inférieur ou égal à la contenance maximale des boîtes.
Exemple (2)

La liste [[7, 1], [5, 3]] est un rangement valide. On a placé les objets de poids 7 et 1 dans une boîte et les deux autres dans une seconde boîte.

La liste [[7, 5], [3, 1]] n'est pas un rangement valide : le poids total de la première boîte est trop grand.

Pour ranger les objets, on impose la méthode suivante :

  • on crée une liste vide boites ;
  • on parcourt les objets dans l'ordre décroissant (on garantit que la liste poids_objets est ainsi triée) :
    • pour chacun d'entre eux, on parcourt l'ensemble des boîtes et l'on se demande pour chacune si l'objet peut y être ajouté :
      • si c'est le cas, on ajoute cet objet,
      • sinon, on passe à la boîte suivante,
  • si l'on a atteint la dernière boîte sans avoir rangé l'objet, on l'ajoute dans une nouvelle boîte à la fin de la liste boites.
Exemple (3)

On applique l'algorithme dans le cas suivant :

🐍 Script Python
    poids_objets = [7, 5, 3, 1]
    poids_max = 8

La liste des boîtes est vide :

boites = []

On ajoute une nouvelle boîte pour cet objet :

boites = [[7]]

On ajoute une nouvelle boîte pour cet objet :

boites = [[7] , [5]]

Cet objet tient dans la deuxième boîte :

boites = [[7] , [5, 3]]

Cet objet tient dans la première boîte :

boites = [[7, 1] , [5, 3]]

Vous devez écrire deux fonctions :

  • poids_boite prend en argument une liste de nombres entiers (une boîte) et renvoie la somme de ces nombres (le poids de la boîte),
  • rangement prend en arguments 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 non triée des boîtes utilisées en appliquant la méthode décrite

Attention

Comme indiqué ci-dessus, on ne triera ni les objets ni les boîtes au risque de faire échouer les tests.

Exemples

🐍 Console Python
>>> poids_boite([])
0
>>> poids_boite([7, 5, 3, 1])
16
>>> rangement([7, 5, 3, 1], 8)
[[7, 1], [5, 3]]
>>> rangement([7, 5, 3, 1], 16)
[[7, 5, 3, 1]]
# Testsbksl-nlassert poidspy-undboite([]) == 0bksl-nlassert poidspy-undboite([7, 5, 3, 1]) == 16bksl-nlassert rangement([7, 5, 3, 1], 8) == [[7, 1], [5, 3]]bksl-nlassert rangement([7, 5, 3, 1], 16) == [[7, 5, 3, 1]]bksl-nlbksl-nl# Tests supplémentairesbksl-nlassert poidspy-undboite([-1, 1]) == 0bksl-nlassert poidspy-undboite([-1, -1]) == -2bksl-nlassert rangement([10, 10, 10], 10) == [[10], [10], [10]]bksl-nlassert rangement([0, 0, 0], 15) == [[0, 0, 0]]bksl-nlassert rangement([9, 4, 3, 3], 10) == [[9], [4, 3, 3]]bksl-nlassert rangement([9, 9, 1, 1], 10) == [[9, 1], [9, 1]]bksl-nlassert rangement([9, 9, 9, 1], 10) == [[9, 1], [9], [9]]bksl-nlbksl-nl ∞/∞

def poidspy-undboite(boite):bksl-nl ...bksl-nlbksl-nlbksl-nldef rangement(poidspy-undobjets, poidspy-undmax):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert poidspy-undboite([]) == 0bksl-nlassert poidspy-undboite([7, 5, 3, 1]) == 16bksl-nlassert rangement([7, 5, 3, 1], 8) == [[7, 1], [5, 3]]bksl-nlassert rangement([7, 5, 3, 1], 16) == [[7, 5, 3, 1]]bksl-nlbksl-nldef poidspy-undboite(boite):bksl-nl total = 0bksl-nl for objet in boite:bksl-nl total += objetbksl-nlbksl-nl return totalbksl-nlbksl-nlbksl-nldef rangement(poidspy-undobjets, poidspy-undmax):bksl-nl boites = []bksl-nlbksl-nl for objet in poidspy-undobjets:bksl-nl indice = 0bksl-nl ajout = Falsebksl-nl while not ajout and indice < len(boites):bksl-nl if poidspy-undboite(boites[indice]) + objet <= poidspy-undmax:bksl-nl boites[indice].append(objet)bksl-nl ajout = Truebksl-nl else:bksl-nl indice += 1bksl-nl if not ajout:bksl-nl boites.append([objet])bksl-nlbksl-nl return boitesbksl-nlbksl-nlbksl-nl# Testsbksl-nlassert poidspy-undboite([]) == 0bksl-nlassert poidspy-undboite([7, 5, 3, 1]) == 16bksl-nlassert rangement([7, 5, 3, 1], 8) == [[7, 1], [5, 3]]bksl-nlassert rangement([7, 5, 3, 1], 16) == [[7, 5, 3, 1]]bksl-nlbksl-nl

A

Il s'agit du problème classique du bin-packing. On applique ici la méthode de la première position : on place chaque objet dans la première boîte pouvant l'accueillir.

Commentaires⚓︎

{{ IDE('exo_corr') }}

La fonction poids_boite ne présente pas difficultés : on crée une variable total initialisée à 0 puis on parcourt les objets et on additionne chaque poids à ce total.

Dans la fonction rangement :

  • on crée la liste boites comme le suggère l'énoncé,
  • on parcourt l'ensemble des objets :
    • pour chacun d'entre eux, on se demande s'il tient dans la dernière boîte. Si ce n'est pas le cas, on en ajoute une nouvelle,
    • on ajoute l'objet à la dernière boîte
  • on la liste boites

Z

Retour en haut de la page