Aller au contenu

Problème d'empaquetage glouton⚓︎

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.

Stratégie gloutonne⚓︎

On utilisera un algorithme glouton consistant à placer chacun des objets dans la première boîte où cela est possible.

Exemple⚓︎

Pour c = 5 et liste = [1, 5, 2] :

  • 1 va dans la première boĂ®te
  • 5 ne peut pas y aller → on ouvre une nouvelle boĂ®te
  • 2 rentre dans la première boĂ®te avec 1

On utilise donc 2 boîtes.

À compléter⚓︎

Compléter la fonction suivante :

###(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
.128013it3a;dv,nî2SR5éwbcy+14q: f-up08)_j9eklohxrP=[s6(]/mg7050g0K0c0e0b0M0U0z0s0M0e0U0U0S010c0b0D010406050U0C0Z0Z0e0Q0t040m0N0M0C0_0N0j050Y101214160~0D04051m1f1p0Y1m0~0g0b0h0.0:0=0@0:0j0!0C0e0!0K0B0D0t0c0O1d0z0O0b0!0O0M1R0O0c0|050)0r0M0K1y0;0?011Q1S1U1S0c1!1$1Y0c0Q1n1M0.190U0D0e0j0@0l011(1A010A0+0K0j0e0Z0K1Y1}1 241*271$2a2c0|0a0z0R0Q0N0D0N0U0b1c0j0z0%1{0Q0Q0K0s2x1f2f0j1n0Y1M2K1@1_1^1Z0g2h1B0b0j292u1Y1v1x0/1)2U2W0j0N2!1Y0D2D1n2I2K2;0 1~2y2$252*0Q130M1Y0e1P2D0A0@030H0H0s2+0K1U2)0N0B0E0B0v0|0z0v1f0e2=2^0}2@2g2`1*2|2~30320K340136383a3c2X3f0B22040z0l3m3o1 3q2I2T013v0e2 1n310O333537390%3F2*3H0d3j0d3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0w3j0w3/1g3;3r2_1z3u0N2}3V3x3Z3z3#3D3(413*3g0o3j0o472;3=2^3S3_4h3}3C3%3b4n3e3g0V3j0V4t493?4c3^4e3w3X3y3A4B403d3H0#3j0#4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0F3j0F4#2J4%4b2%4*4f3`3|4j3~4l4D4=0B0J3j0J4`3Q4w3@4 4Q3{4S4k4C3)4F3h0E0|0v0E5c4|4x4+515j545l4E3H0v3i045D5t4a5v504z534U4;423h3J0v3M0Y3n3:4$5I5f4y4-4A4:565P0v3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 483P1q2/1f2!2N0g1_2S5f4C2Z1w1n2.0K2:3p601n4C6v2g0b0g0@372I5C3x6C6E675B3g3i0z2l0K6K5A575E3/62250L0|0%0A6x5;4~0q3j6%6X3u0A0|0K0Z1~0x0C0(0K0Q6,5e4)0{040W6|4(630|1U0U0c0K0H130=0K0U724}256 0i6x0z6(2{0|0s7f3S6 0G0y6x0~6e2J5I6J016F2^3H3J5i7A5%683g226P2b6R7B6L577F5 6-0@6*3K0z7Y7q5f0U0g0|026@0N0c0f7)0C7+7-7*7,0n290h0N0b1%1$6P0N0Z0r2D0z0Z2V0b2~2z1%0r0N0k780-0j0p0s7d0U0*2D0-2t0C6{7x3q8q7z6D7P6G3g5+7G8u7I6M0B3,7M2c6S5`4o8D1Y7T6}4~7$3j7Y0z6;6?6^780Q0z1$0-0N0r0I0(0-2A0:8Y0b777|8-787a1)7d0i0z8j0s0O1 0c7v7q7H0H8w0B5|8z8H5O8J448F7O8B57958M73258P7X7Y6@1%8{0e9m0z8a8c1%0D0K1b1{0j780j0b8X0e0C830e0P86110.0z0L0+0N0!0Q2b2c0U7.7:9V7,9X0f8 8s3R91936a967P6T5P4q9b975(8J9*5.8R7l7U3T0|1e8q9`8N250N0|0S7k7m3u0r75297!6~0|719$a13u758:797b0U7dac4~7s9#2?9%8A927D4G6Iav9-8J4H9:9,8I5n4H2K3n9_a73^9}0r0H8a2wao9 aM01a304a5aU9{840|5s8q7wat4w9(ax0B4Y4R91aB5n4YaE9d5Pa:3NaL9{0j0|aR8da69{aXaZ2;a09h1*6 0Tb4ah0@a$04a(b8aV6Z040A4ebebaaN040Hbq7g1*0N7W2Vbv4xa9049R1D0Kap7haebIai049~a+br01ara!bfbR0|0Xas6wau6K934@a;aAaG3H4@a_7Q5Pb%a}8Rbl0|bo8pbka 0|ambHbTbQby0|bAb bwbs768;b}7eagbQ6 7u9 a*bZa,av9359b(9;7J58236Qcn8Cclb;9_7Zb{040bbB5fb6cB4)bhbj49cb2ya-1 5C5pcmaF985n5rcq7Ncs6UcOcvcwb?040q1Q1$cE74czc*a27(0M7,c-bM0jaPb2aTb`bUc1041 0gc=bsc_cabPc5bV04bdcJ4xc2bL0@6 bXc43SaX0ud19|04b}dlaX020!c;dh5Z7oddd7ceb8cg6fb!8va.5DazcW5)6OcrcQ9=cS6V9^cwdRaVb0c,du4)cDdWc+cAdZc.04dkd$1*bh3la)90cjdF7F31a=b*6N7LdLa`8J5S8LaKdRb9d6bm0b6$d*bsd#c{c0a4b73pe2dbbNc^7`b3da5fcdbYdCcib#dF8yd?b)cR5C8Ed{b.d}8ydQe1b=cyc@aQejc`eeaVdYead6dUeHd3dp0|d)eO3Sd,eo7ydD7CcM6N95eudId}9aeza?5C9fe0dScyeSeladd8dxdUe9chccbWeTaYdldUe^d57r0|d9f7dvdVfbe`dgeWcCeUf4b|8?7kdBe!eqdEe%3h9*e*dMco0v9/e.d^ftd 9kef5fbm2D0c8obOeLeGeiaSd4eefo2K6z6g6u6i6r1f0c6lfZ2Q2L0e1#fW0Y6j7w0%0)0+0U04.
Python
1
2
3
4
5
6
>>> 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