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
.128013fdq6nmi7é4=]3y_ 9pu08ts5[î/v1b(jP)l;gow-ahR:+rxS2cek,050c0Z0w0P0h0J0x0q0Y0J0P0x0x0l010w0h0s010406050x0t0g0g0P0U0o040W0M0J0t0_0M0f050B101214160~0s04051m1f1p0B1m0~0c0h0C0.0:0=0@0:0f0L0t0P0L0Z0O0s0o0w0Q1d0q0Q0h0L0Q0J1R0Q0w0|050)0E0J0Z1y0;0?011Q1S1U1S0w1!1$1Y0w0U1n1M0.190x0s0P0f0@0X011(1A010b0+0Z0f0P0g0Z1Y1}1 241*271$2a2c0|0a0q0H0U0M0s0M0x0h1c0f0q0%1{0U0U0Z0Y2x1f2f0f1n0B1M2K1@1_1^1Z0c2h1B0h0f292u1Y1v1x0/1)2U2W0f0M2!1Y0s2D1n2I2K2;0 1~2y2$252*0U130J1Y0P1P2D0b0@030p0p0Y2+0Z1U2)0M0O0D3f0|0q0D1f0P2=2^0}2@2g2`1*2|2~30320Z340136383a3c2X3f0O22040q0X3l3n1 3p2I2T013u0P2 1n310Q333537390%3E2*3G0n3i0n3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0k3i0k3.1g3:3q2_1z3t0M2}3U3w3Y3y3!3C3%403)3g0y3i0y462;3;2^3R3^4g3|3B3$3b4m3e3g0e3i0e4s483=4b3@4d3v3W3x3z4A3 3d3G0i3i0i4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0v3i0v4!2J4$4a2%4)4e3_3{4i3}4k4C4;0O0r3i0r4_3P4v3?4~4P3`4R4j4B3(4E3f0u0|0D0u5b4{4w4*505i535k4D3G0D0D5p3k0B3m3/4#495u4 4y524T4:413f3I0D3L5G3N4`5K5e4x4,4z4/555R0D3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560D4G5-4I6c2?1s2/1f2!2N0c1_2S5e4B2Z1w1n2.0Z2:3o5 1n4B6H2g0h0c0@372I5B3w6O6Q665A3g5D0q2l0Z6W6k5*1Y5~6f1*0!0|0%0b6J5:4}0N3i6?6-3@0b0|0Z0g1~0d0t0(0Z0U6{5d4(0{040F784%620|1U0x0w0Z0p130=0Z0x7e4|257b0#6J0q6@2{0|0Y7r3R7b0I0S6J0~6d2J5K6V016R2^3G3I5h7M5(673g226#2b6%7N6X567R6,796^3i0q7-7C5e0x0c0|02730M0w0K7@0t7_7{7^7`0R290C0M0h1%1$6#0M0g0E2D0q0g2V0h2~2z1%0E0M0A7k0-0f0j0Y7p0x0*2D0-2t0t777J3p8B7L6P7#6S3g5,7S8F7U6Y0O3+7Y2c6(5_4n8O6+5H6|017;7,7-7072747k0U0q1$0-0M0E0G0(0-2A0:8,0h7j878`7k7m1)7p0#0q8u0Y0Q1 0w7H7C7T0p8H0O5{8K8S5Q8U438Q7!8M569f7)7f258!3J7-0q731%950P9x0q8l8n1%0s0Z1b1{0f7k0f0h8+0P0t8e0P0V8h110.0q0!0+0M0L0U2b2c0x7|7~9*7`9,0K998D3Q9b9d699g7#6)8U4p9l9h5)9|8W8C2?9=8L9c7P4F6Ua69{5m4G9~9`8Tada29v7x8Y0f0|1e8Bal7*250M0|0l7w7y3t0E7h297/7a0|7d9;as3t7h8}7l7n0x7paD4}7E9:a44v9?a80O4X4Q9bac4W236$9 7VaYaj9vay3@ao0E0p8l2waPaqa/01au04awa`8Y8f0|5r8B7IaU6Na69d4?a!abah3G4?af9n5Rbb3Maka{an04a@8oax8Ya}a 2;ar9r1*7b0zbsaI0@b204b4bwa{6/040b4dbCbya:040pbO7s1*0M6_042VbT4waA049$1D0ZaQ7taFb+aJ04apb7bU0@aSb0bD017b0maT6Ia56W9d58bca*8N58bh7$5Rc3bla.8YbKbM8AbIam0|aNb*b_bPa|bXbZcnb?3SaK8{8 7o7qaHco7b7Gaqb6b aVb9aX5qaac56l5oc8a$6Z5o2K3makbmcjbYb!5ebucZ4(bFbH48cA2yaW1 5B5Dc4ag9i5m5Ca(7ZcM5*c:cccVbxctbK0N1Q1$c$7gcYcs3Ra}020J7`d67zb:a=bqa_cib`bW0|1 0cdfb/djczb=7D0|bBc+4w0|0hb.b@0|b}d9c!0|0TdrbQcldLa|7?0LdedH5;7AdDb{0|cDbwcF3O8Ec1cJ7R31a#be6Z7Xa)c=a0c@7(cUc cVbndBdOc#dTd7dCd atdJdObF5F4t9acIc.6Z8Jd+bdc?5B8Pd:bi8U5+a-c bJdB6=e2b/e1dlcobubv3od0dAdha?85brdz5ecCb~d$c08GcJ9feec{el9kejc9eRend_7.cX0fdieEdkeza{d~evctboe!eDa^due(bte4esbE0h5peJ7KeL7Oeb3f9^ePd;a+0D9}eTcQf1eWcWb`bodtdWbAdWboeucGcBdFd}avdOfee$e;eKb`fheGdUd8dveHfne^dP04dKfDbodNcEe9d(f06mcLf48NfOcPd-3f6nc~eA5ebK2D0w8zb;e=fda;e/eFe88D0B6L1q6t0B6v1f0w6xf_2Q2L0P1#6G6u6D7I0%0)0+0x04.
# Tests
(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)