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

Python Console Session
>>> 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

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013kg[:î r);Sé/q(lo4y,6b=ac1x5+ujd3t28_Pw7evp-fh09mnR]is050F0O0H0x0!0p0#0g0y0p0x0#0#0w010H0!0Q010406050#0D0W0W0x0h0s040k0q0p0D0_0q0X050m101214160~0Q04051m1f1p0m1m0~0F0!0P0.0:0=0@0:0X0c0D0x0c0O0R0Q0s0H0T1d0g0T0!0c0T0p1R0T0H0|050)0v0p0O1y0;0?011Q1S1U1S0H1!1$1Y0H0h1n1M0.190#0Q0x0X0@0I011(1A010S0+0O0X0x0W0O1Y1}1 241*271$2a2c0|0a0g0L0h0q0Q0q0#0!1c0X0g0%1{0h0h0O0y2x1f2f0X1n0m1M2K1@1_1^1Z0F2h1B0!0X292u1Y1v1x0/1)2U2W0X0q2!1Y0Q2D1n2I2K2;0 1~2y2$252*0h130p1Y0x1P2D0S0@030K0K0y2+0O1U2)0q0R0z3f0|0g0z1f0x2=2^0}2@2g2`1*2|2~30320O340136383a3c2X3f0R22040g0I3l3n1 3p2I2T013u0x2 1n310T333537390%3E2*3G0G3i0G3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0r3i0r3.1g3:3q2_1z3t0q2}3U3w3Y3y3!3C3%403)3g0B3i0B462;3;2^3R3^4g3|3B3$3b4m3e3g0u3i0u4s483=4b3@4d3v3W3x3z4A3 3d3G0N3i0N4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0J3i0J4!2J4$4a2%4)4e3_3{4i3}4k4C4;0R0V3i0V4_3P4v3?4~4P3`4R4j4B3(4E3f0U0|0z0U5b4{4w4*505i535k4D3G0z0z5p3k0m3m3/4#495u4 4y524T4:413f3I0z3L5G3N4`5K5e4x4,4z4/555R0z3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560z4G5-4I6c2?1s2/1f2!2N0F1_2S5e4B2Z1w1n2.0O2:3o5 1n4B6H2g0!0F0@372I5B3w6O6Q665A3g5D0g2l0O6W6k5*1Y5~6f1*0b0|0%0S6J0g5:620S0|0O0W1~0n0D0(0O0h6J6^250{040o746-3@0|1U0#0H0O0K130=0O0#7a5d4(770t6?753t0|0y7n4%4}770i0e6J0~6d2J5K6V016R2^3G3I5h7I5(673g226#2b6%7J6X567N6,7o4}0M3i0g7*7x4|250#0F0|026 0q0H0j7=0D7@7_7?7^0Y290P0q0!1%1$6#0q0W0v2D0g0W2V0!2~2z1%0v0q0f7g0-0X0l0y7l0#0*2D0-2t0D737F3p8z7H6P7X6S3g5,7O8D7Q6Y0R3+7U2c6(5_4n8M6+5H7b017/7)7*6|6~707g0h0g1$0-0q0v0E0(0-2A0:8*0!7f858^7g7i1)7l0t0g8s0y0T1 0H7D7,0g7P0K8F0R5{8I8Q5Q8S438O7W8K569e7#7y7.7:3J7*0g6 1%930x9w0g8j8l1%0Q0O1b1{0X7g0X0!8)0x0D8c0x0A8f110.0g0b0+0q0c0h2b2c0#7`7|9)7^9+0j978B3Q9a9c699f7X6)8S4p9k9g5)9{8U8A2?9;8J9b7L4F6Ua59`5m4G9}9_8Raca19u6@8W0X0|1e8zak7$250q0|0w7sal0v7d29985e77799:ar7u047e8|7j0#7laB7p0|0i9/a34v9=a70R4X4Q9aab4W236$9~7RaXai9u7t7c040X0v0K8j2waNapa.01at04ava`8W8d0|5r8z7EaT6Na59c4?aZaaag3G4?ae9m5Rbb3Maja{am04a@8mawaG0@a}a 2;aq9q1*770dbsbz0@b204b4bxa{6/040S4dbD7-aH0KbP3R0q7(042VbT5!ay049#1D0OaO7z0|aEb7bQa/aob.3R7AbZaP040ZaS6Ia46W9c58bca)8L58bh7Y5Rc1bla-8WbLbN8ybJal0|aLb)b0bta|bWbYclbE3S7d8{7hcj7maFcr777Capb6b}aUb9aW5qa9c36l5oc6a#6Z5o2K3majbmchbXb^4}bvcX25bGbI48cy2yaV1 5B5Dc2af9h5m5Ca%7VcK5*c.cacTbyb/01bL0M1Q1$c!aH0!d5bu7;0p7^d8csa:a=bqa_cgcmbV0|1 0Fddbodhcxb=aC0|bCc)4w0|d7dxdub`dda}0Cdpci8~dE7;0cdccqc bo7wdBb_cBbxcD3O8Cb cH7N31a!be6Z7Ta(c:9 c=7!cSc}cTbndzdKa~dHcWdObU0|dGd|5ebG5F4t98c+0X5B8Hd$bdc;e8c@8Pd,a*5+a,c}bKdz6=e05;d@eocYaubw3oc~dydfa?83brdSb+04dUc(b=e65B9eeac_8S0z9jd+bieN9od:d;cbcmboa;eza^dseva{cZer2{andgeAdie%8WdFdde2b|dXb~8EcH9@eLeg8L0z9|eQc7eN9@5WeVd?bpe.e$e_cmbBb*e+d{dtb_b{e*1*e)djcrdqfbfgbAdvfta/dAfjeDflfpc e=fma/cj6?dW7Ge`7Kc,6Z6n9^eRc=adf3cO3ffPf7eWcrbL2D0H8xb;e:eXe,e!eBe48B0m6L1q6t0m6v1f0H6xf`2Q2L0x1#6G6u6D7E0%0)0+0#04.