Mise en boîtes
Exercice
Sujet inspiré de https://prologin.org/train/2023/qualification/mise_en_boites
Cyril et 5 de ses amis sont en train de choisir leur film quand Cyril se rend compte que les restes du repas qu'ils ont dégusté juste avant attendent encore sur la table basse. Pour conserver leurs aliments, il faut les mettre dans des boîtes et les ranger au réfrigérateur. Qui sait, ils pourraient en avoir besoin si d'aventure ils décidaient de se lancer dans un grand voyage ! Le hasard faisant bien les choses, ils ont autant de boîtes que de restes. Tous les récipients ne sont toutefois pas forcément de la bonne taille.
Aidez nos 6 amis à remplir le plus de boîtes sachant qu'un aliment d'un certain volume ne peut entrer que dans une boîte d'un volume supérieur ou égal. Afin de conserver au mieux le goût de la nourriture, on ne mettra qu'un aliment dans chaque boîte.
Complétez dans tp12_vers_13.py, la fonction mise_en_boite(restes, boites) pour que sa spécification et les tests unitaires fournis soient satisfaits.
def mise_en_boite(restes, boites):
"""
Renvoie le nombre maximal de boites pour placer chaque reste
d'aliment dans une boite qui peut le contenir
Paramètres :
restes : liste de volumes d'aliments (entiers positifs)
boites : liste de volumes de boites (entiers positifs)
Retour: un entier positif
"""
Exemple 1 :
>>> mise_en_boite([832, 342, 500], [750, 250, 500])
2
Ici on peut mettre l'aliment de 500 cm³ dans la boîte de 500 cm³. Le reste de 342 cm³ peut être rangé dans la boîte de 750 cm³. On peut aussi mettre le reste de 342 cm³ dans la boîte de 500 cm³ et celui de 500 cm³ dans la boîte de 750 cm³.
Exemple 2 :
>>> mise_en_boite([487, 601, 584, 819, 601], [750, 500, 700, 65, 700])
4
Voici une liste possible de paires (reste, boîte) : (487, 500), (584, 650), (601, 700), (601, 700). On aurait pu également mettre un aliment de 601 cm³ dans la boîte de 750 cm³. Le mets de 819 cm³ ne peut être mis en boîte.
def misepy-undenpy-undboite(restes, boites):bksl-nl """bksl-nl Renvoie le nombre maximal de boites pour placer chaque restebksl-nl d'aliment dans une boite qui peut le contenirbksl-nlbksl-nl Paramètres :bksl-nl restes : liste de volume d'aliments (entiers positifs)bksl-nl boites : liste de volume de boite (entiers positifs)bksl-nlbksl-nl Retour: un entierbksl-nl """bksl-nl # à compléterbksl-nlbksl-nlbksl-nldef testpy-undmisepy-undenpy-undboite():bksl-nl """Tests unitaires pour mise en boite"""bksl-nl restes1 = [832, 342, 500]bksl-nl boites1 = [750, 250, 500]bksl-nl assert misepy-undenpy-undboite(restes1, boites1) == 2bksl-nl restes2 = [487, 601, 584, 819, 601]bksl-nl boites2 = [750, 500, 700, 65, 700]bksl-nl assert misepy-undenpy-undboite(restes2, boites2) == 4bksl-nl print("Tests réussis pour misepy-undenpy-undboite")bksl-nlbksl-nldef misepy-undenpy-undboite(restes, boites):bksl-nl """bksl-nl Renvoie le nombre maximal de boites pour placer chaque restebksl-nl d'aliment dans une boite qui peut le contenirbksl-nlbksl-nl Paramètres :bksl-nl restes : liste de volume d'aliments (entiers positifs)bksl-nl boites : liste de volume de boite (entiers positifs)bksl-nlbksl-nl Retour: un entierbksl-nl """bksl-nl # à compléterbksl-nl # BEGIN CUTbksl-nl # on trie d'abord les listes restes et boites par ordre croissantbksl-nl restespy-undtri = sorted(restes)bksl-nl boitespy-undtri = sorted(boites)bksl-nl ir = 0bksl-nl for b in boitespy-undtri:bksl-nl # Choix glouton : on choisit la boite b si elle peut contenirbksl-nl # le plus petit aliment restant ( restespy-undtri[ir] car restespy-undtri dans l'ordre croissant)bksl-nl # choix jamais remis en cause par la suite : si la boite ne peut pas contenirbksl-nl # le plus petit aliment, elle ne pourra pas contenir les autresbksl-nl if restespy-undtri[ir] <= b:bksl-nl ir = ir + 1bksl-nl return irbksl-nl # END CUTbksl-nlbksl-nlbksl-nldef misepy-undenpy-undboite2(restes, boites):bksl-nl """bksl-nl Renvoie le nombre maximal de boites pour placer chaque restebksl-nl d'aliment dans une boite qui peut le contenirbksl-nlbksl-nl Paramètres :bksl-nl restes : liste de volume d'aliments (entiers positifs)bksl-nl boites : liste de volume de boite (entiers positifs)bksl-nlbksl-nl Retour: un entierbksl-nl """bksl-nl # à compléterbksl-nl # BEGIN CUTbksl-nl # on trie d'abord les listes restes et boites par ordre décroissantbksl-nl restespy-undtri = sorted(restes, reverse=True)bksl-nl boitespy-undtri = sorted(boites, reverse=True)bksl-nl ib = 0bksl-nl for r in restespy-undtri:bksl-nl # Choix glouton : on choisit l'aliment r s'il peut être contenubksl-nl # dans la plus grande boite restante ( boitespy-undtri[ib] car boitespy-undtri dans l'ordre décroissant)bksl-nl # choix jamais remis en cause par la suite : si l'aliment est trop grand pour la plus grande boitebksl-nl # il le sera pour les autresbksl-nl if boitespy-undtri[ib] >= r:bksl-nl ib = ib + 1bksl-nl return ibbksl-nl # END CUTbksl-nlbksl-nl
A
Z