Empaqueter

On dispose d’un ensemble d’objets dont on connaît, pour chacun, la masse. On souhaite ranger l’ensemble de ces objets dans des boites identiques de telle manière que la somme des masses des objets contenus dans une boîte ne dépasse pas la capacité c de la boîte. On souhaite utiliser le moins de boîtes possibles pour ranger cet ensemble d’objets.

Pour résoudre ce problème, on utilisera un algorithme glouton consistant à placer chacun des objets dans la première boîte où cela est possible.

Par exemple, pour ranger dans des boîtes de capacité c = 5 un ensemble de trois objets dont les masses sont représentées en Python par la liste [1, 5, 2], on procède de la façon suivante :

Le premier objet, de masse 1, va dans une première boite.
Le deuxième objet, de masse 5, ne peut pas aller dans la même boite que le premier objet car cela dépasserait la capacité de la boite. On place donc cet objet dans une deuxième boîte.
Le troisième objet, de masse 2, va dans la première boîte.

On a donc utilisé deux boîtes de capacité c = 5 pour ranger les 3 objets.

Compléter la fonction Python empaqueter(liste_masses, c) suivante pour qu’elle renvoie le nombre de boîtes de capacité c nécessaires pour empaqueter un ensemble d’objets dont les masses sont contenues dans la liste liste_masses.

Exemples

🐍 Console Python

>>> empaqueter([1, 2, 3, 4, 5], 10)
2
>>> empaqueter([1, 2, 3, 4, 5], 5)
4
>>> empaqueter([7, 6, 3, 4, 8, 5, 9, 2], 11)
5

Compléter le code ci-dessous

Évaluations restantes : 5/5

.1280130ldy1,4]kjé/weibmc_:35qaPr+ 7=9o[fgt28;6sSRh)(pîunxv050d0o0K0y0p0c0P0C0s0c0y0P0P0E010K0p0V010406050P0X0r0r0y0A0e040Q0G0c0X0^0G0Y050m0 1113150}0V04051l1e1o0m1l0}0d0p0!0-0/0;0?0S0p0J0S0c1C0S0K0{050(0q0c0o1x0:0=011B1D1F1D0K1L1N1J0K0A1m0K0S0-180P0V0y0Y0?0L011P1z010I0*0o0Y0y0r0o1J1,1.1?1R1_1N1|1~0{0a0C0z0A0G0V0G0P0p1b0Y0C0$1*0A0A0o0s2j1e210Y1m0m1(2w1#1%1$1K0d230?1F0Y1{2g1J1u1w0.1Q2G0p2I0Y0G2M1J0V2p1m2u2w2!0~1-2k2O1@2T0A120c0{0C0f2t2(0|2%222*1R2,2.2:0L2?1.2^2u2F012}0y2/040C0v312v0}342{0?37390C0h3d332(353j2:0w3n3f3p3h360G2-382:0O3u2_2)1y2|3z2~3a0D3E3g3H3i3J3B3a0M3N3w3P3y3A3k0F3V2`3X3r040f0b3$3G2P3Y3K0f2=1f2@3v3%3/3)0f303@323_3.2+3R390f3c3 3e3F3q440{0f3m483o3`433Z4d3t4g414b4k3*3D4g1p2Y1e2M2z0d1%2E3x0s2U1 1m4x1n4v2$4t4D0$2Z3W3/0j0{0$0I3n0C4a3x0Y0I0{0o0r1-0x0X0%0o0A3n4X3X0`040U4.3O3{0{1F0P0K0o0t120;0o0P4@4P1@4;0g4V4/4_040s544i1R4;0T0u3-350n2:0C5o5e421R0P0d0{024)0G0K0N5w0X5y5A5x5z0R1{0!0G0p1O1N0C2T0r0q2p0C0r2R0p2.2l1O0q0G0W4}0,0Y0l0s520P0)2p0,2f0X4-4n5a1@5t5n5o4$4(4*4}0A0C1N0,0G0q0k0%0,2m0/620p4|5M6d4}4 1Q520g0C5-0s0S1.0K5k3x5`3a5o0C4)1O6o0y6y0C5!5$1O0V0o1a1*0Y4}0Y0p610y0X5T0y0Z5W100-0C0j0*0G0J0A1}1~0P5B5D6+5z6-0N3u066w4W4^2+0{1d4g6@551R0G0{0E596^2|0q4`1{5q354;4?4t743i4`6g4~500P52793x5h3u6?5^2|6`0q0t5!2i7l6|7r0?7004727z7e015U0{3,4n7q7G0Y0{7w5%736~7B717S5f0?4;0H7W5r0?7I047K2!6}7X014R040I3z7#3q0{0t7?3x0G5m042R7`3(76046%0Y0J0o7m4:0{7c2$7N6`883/7o7F7T014;0i7p6w7A7.0{7;5?7+8p7O047j878i7-7|0{7 8A7$367g6e6i51537d8j4;5j6|6=6?8o8d7~803/7C7E8u7G7(7*3^8T8U8j7/0n1B1N8X6_8W8F357C020c5z8;7s040Y7u7Q7y8#8j8C041.0d8}7f04928M8c8O0{7!8N7-8w0p8f560{8m8@7{0{0B9a8H8x6j9v8_0J8|9r3(0{5d9j8G8P4V8S8*7M8j9l9z7V9D5b9m9S1@7C9u9V1R7(3?2!9L8T8p7/0p4U9Z9b9U948B718!2@7,8G8w907v5K7R9H7a0{8Q9%9M9)8V9|9d9Q7D9v9{919~939^8p9X9v9#8n8*8v7Paf9e2@8p7Z9n8~9:as7G8laa9@329_7@9caqav7Y9haI9wax32at9paa9Y9;9`0{8y9K9N7-7/2p0K5=6{aTaFa8aH5@0m4M0o2w2Xa:4w1v4y2z2C2x0y1Ma?0m4x0}b00%0)0+04.