Le problème du sac à dos⚓︎
Exemple utilisé pour cette partie
Pour cette partie, nous utiliserons l'exemple suivant, qui correspond à celui du cours.
objets = [{"nom": "Objet 1", "valeur": 10, "poids": 9},
{"nom": "Objet 2", "valeur": 7, "poids": 12},
{"nom": "Objet 3", "valeur": 1, "poids": 2},
{"nom": "Objet 4", "valeur": 3, "poids": 7},
{"nom": "Objet 5", "valeur": 2, "poids": 5}]
Générer toutes les solutions
Afin de tester toutes les solutions possilbles, nous allons générer des listes de booléens indiquant s'il faut prendre tel ou tel objet.
Exemples d'utilisation
>>> import itertools
>>> list(itertools.product([False, True], repeat=3))
[(False, False, False), (False, False, True), (False, True, False),
(False, True, True), (True, False, False), (True, False, True),
(True, True, False), (True, True, True)]
Le module itertools définit de nombreuses fonctions qui permettent de générer des listes. Ici, on utilise la fonction product qui prend en paramètre une liste valeurs et un entier n, et qui génère la liste de toutes les combinaisons de n éléments de valeurs, avec éventuellement des répétitions.
Dans notre cas, chaque booléen correspondra à un objet de la liste d'objets et indiquera s'il faut prendre ou pas cet objet.
Exercice 3
Compléter la fonction evaluer_solution qui prend en paramètres une liste de dictionnaires liste_objets et une liste de booléens solution de même taille, et qui renvoie le poids, la valeur et la liste des noms d'objets pris dans la solution solution.
Exemples d'utilisation
>>> evaluer_solution(objets, [True, False, False, True, False])
(16, 13, ['Objet 1', 'Objet 4'])
>>> evaluer_solution(objets, [False, False, True, True, True])
(14, 6, ['Objet 3', 'Objet 4', 'Objet 5'])
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
.128013 ;)3=9+lwjqn8gv,S."5/:rf7uemkdas p
h10itP(_y2[46cb]o 030x0u0H0y0G0b0z0A0Q0b0y0z0z080m0H0G0B0m020C030z0t0v0v0y0q0L020k0T0b0t0-0T0f030o0@0_0{0}0=0B02031d161g0o1d0=0x0G0i0$0'0)0+0D0G0h0D0b1u0D0H0:030X0R0b0u1p0(0*0m1t1v1x1v0H1D1F1B0H0q1e0H0D0$100z0B0y0f0+0M0m1H1r0m0r0Z0u0f0y0v0u1B1!1$1*1J1-1F1:1=0:040A0I0q0T0B0T0z0G130f0A0V1Y0q0q0u0Q2a161^0f1e0o1W2n1T1V1U1C0x1`0+1x0f1/271B1m1o0%1I2x0G2z0f0T2D1B0B2g1e2l2n2R0?1#2b2F1+2K0q0`0b0:0A0E2k2V0;2U1_2X1J2Z2#2%0M2)1$2+2l2w0m2:0y2$020A072@2m0=2`2.0+2}2 0A0O332_2V2{392%0n3d353f372|0T2!2~2%0P3k2,2W1q2/3p2;300s3u363x383z3r300g3D3m3F3o3q3a093L2-3N3h020E0F3d1h2P162D2q0x1V2v3n0Q2L1?1e3%1f3#2T172*033,0V2Q3M2G0m0w0:0V0r3d0A3v3g0r0:0u0i2~0t0u0q0K0z10120G143Z3E3~0/020J4m3}2Y0:1x0z0H0u0K0T0R0d0W0z4s3T4o0:0j44463n0f0:4h112j3@2^4M3N4p060p3k0A4#454n4u02260G0x4F4T2m4%4t1J0T0:084L4'1J0v0G0:3Y4.0;4$4:4H4(4b1F0t0q4_4;0+4?024^50533w3~4|4~4!4$4V3~4O024B4D0H0z4g0u1F0Q5a544=4@5A5i1+4p0N0S5m4#5o1+40020r3p5E3g0:0G5S3n0T0c5U155g5M2/0R0:0q1$0h0u4G5F1J4p4r505%385(021}5.2{5;5|4N4v0G4x4z5s4E5 4W0:064Y5K525h2{5O0G435$4`384P4i4S2T6k0m5H675p5U6t5G0:0S4Z500C6d6D6e604)0T4+4-2R6F3N5d5f6L5@2|0:4*4,5W6N0:0a6W6u5`624y4A4C665?6q6s6+5b6S025V6.5B0+4p0S0N6w1J0z1(02000e0t0T0H056U0z7173756|6^6y6c6E6M6#560u586!1+6O7m2/0:7j7l6j6/5d6Z7u6@6:4w6'655u7c6r0:6{6?5/6l6;7F6_7I6p6/6~0:7974057s0q7U7b7J5}7e6B7g526R5q7D5v0z5x2h7F5d0l7F5q0y0B0B1/0x7N0:5=7Q7z5q7B646)7E7#3n6-817K6:6=8b7$026`7F7S70727V2K0v7Z057~8h066c6R5O2g0H585#6Q6q5q778s4K7y8c5q7X8G7p7L7,5w5y3u0o3`0u2n2O8V3$1n3'2q2t2o0y1E8Y0o3%0=8+0W0Y0!02.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)3=9+lwjqn8gv,S."5/:rf7uemkdas p
h10itP(_y2[46cb]o 030x0u0H0y0G0b0z0A0Q0b0y0z0z080m0H0G0B0m020C030z0t0v0v0y0q0L020k0T0b0t0-0T0f030o0@0_0{0}0=0B02031d161g0o1d0=0x0G0i0$0'0)0+0D0G0h0D0b1u0D0H0:030X0R0b0u1p0(0*0m1t1v1x1v0H1D1F1B0H0q1e0H0D0$100z0B0y0f0+0M0m1H1r0m0r0Z0u0f0y0v0u1B1!1$1*1J1-1F1:1=0:040A0I0q0T0B0T0z0G130f0A0V1Y0q0q0u0Q2a161^0f1e0o1W2n1T1V1U1C0x1`0+1x0f1/271B1m1o0%1I2x0G2z0f0T2D1B0B2g1e2l2n2R0?1#2b2F1+2K0q0`0b0:0A0E2k2V0;2U1_2X1J2Z2#2%0M2)1$2+2l2w0m2:0y2$020A072@2m0=2`2.0+2}2 0A0O332_2V2{392%0n3d353f372|0T2!2~2%0P3k2,2W1q2/3p2;300s3u363x383z3r300g3D3m3F3o3q3a093L2-3N3h020E0F3d1h2P162D2q0x1V2v3n0Q2L1?1e3%1f3#2T172*033,0V2Q3M2G0m0w0:0V0r3d0A3v3g0r0:0u0i2~0t0u0q0K0z10120G143Z3E3~0/020J4m3}2Y0:1x0z0H0u0K0T0R0d0W0z4s3T4o0:0j44463n0f0:4h112j3@2^4M3N4p060p3k0A4#454n4u02260G0x4F4T2m4%4t1J0T0:084L4'1J0v0G0:3Y4.0;4$4:4H4(4b1F0t0q4_4;0+4?024^50533w3~4|4~4!4$4V3~4O024B4D0H0z4g0u1F0Q5a544=4@5A5i1+4p0N0S5m4#5o1+40020r3p5E3g0:0G5S3n0T0c5U155g5M2/0R0:0q1$0h0u4G5F1J4p4r505%385(021}5.2{5;5|4N4v0G4x4z5s4E5 4W0:064Y5K525h2{5O0G435$4`384P4i4S2T6k0m5H675p5U6t5G0:0S4Z500C6d6D6e604)0T4+4-2R6F3N5d5f6L5@2|0:4*4,5W6N0:0a6W6u5`624y4A4C665?6q6s6+5b6S025V6.5B0+4p0S0N6w1J0z1(02000e0t0T0H056U0z7173756|6^6y6c6E6M6#560u586!1+6O7m2/0:7j7l6j6/5d6Z7u6@6:4w6'655u7c6r0:6{6?5/6l6;7F6_7I6p6/6~0:7974057s0q7U7b7J5}7e6B7g526R5q7D5v0z5x2h7F5d0l7F5q0y0B0B1/0x7N0:5=7Q7z5q7B646)7E7#3n6-817K6:6=8b7$026`7F7S70727V2K0v7Z057~8h066c6R5O2g0H585#6Q6q5q778s4K7y8c5q7X8G7p7L7,5w5y3u0o3`0u2n2O8V3$1n3'2q2t2o0y1E8Y0o3%0=8+0W0Y0!02.
Exercice 4
Compléter la fonction sac_a_dos_brute qui prend en paramètres une liste de dictionnaires liste_objets et un entier poids_max, et qui renvoie la valeur, le poids et les objets sélectionnés pour la meilleure solution possible avec la limite de poids poids_max.
Exemple d'utilisation
>>> sac_a_dos_brute(objets, 15)
(12, 14, ['Objet 1', 'Objet 5'])
Dans cet exemple, on voit que la meilleure solution consiste à prendre les objets 1 et 5, pour une valeur totale de 12, et un poids de 14, avec une limite fixée à 15.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)3=9xlTjwn8gv,S."5/:rCf7Fuemkdas p
h10itP(_y2[46cb]o 030z0w0J0A0I0b0B0C0S0b0A0B0B080m0J0I0D0m020E030B0v0x0x0A0q0N020k0V0b0v0/0V0f030o0_0{0}0 0@0D02031f181i0o1f0@0z0I0i0'0)0+0-0F0I0h0F0b1w0F0J0=030Z0T0b0w1r0*0,0m1v1x1z1x0J1F1H1D0J0q1g0J0F0'120B0D0A0f0-0O0m1J1t0m0s0#0w0f0A0x0w1D1$1'1,1L1/1H1=1@0=040C0K0q0V0D0V0B0I150f0C0X1!0q0q0w0S2c181`0f1g0o1Y2p1V1X1W1E0z1|0-1z0f1;291D1o1q0(1K2z0I2B0f0V2F1D0D2i1g2n2p2T0^1%2d2H1-2M0q0|0b0=0C0G2m2X0?2W1{2Z1L2#2%2(0O2+1'2-2n2y0m2=0A2'020C072_2o0@2|2:0-2 310C0Q352{2X2}3b2(0n3f373h392~0V2$302(0R3m2.2Y1s2;3r2?320t3w383z3a3B3t320g3F3o3H3q3s3c093N2/3P3j020G0H3U3y2I3Q3C0G2*192,3n3V3%3X0G2^3+2`3-3$2!3J310G343?363x3i3{0=0G3e3 3g3.3`3R443l473^424b3Y3v471j2R182F2s0z1X2x3p0S2N1^1g4o1h4m2V4k4u0X2S3O3%0y0f0=0I0x280q0J3f0C413p0f4J022b0w4O0V1#3m4f3p0y0=0X0s4Q4S3W0s0=0B0A0S0M0A0M0z290M0T0q140w3f4-3%0;020L513G3/0=1z0B0J0w0M0V0T0d0Y0B574G1-540j4,582!0=280I0z0B0M0|0a5l491L54060p3m0C5I4R5r2;0=17475K5m1L0V0=085q5R3a0T5a1;5B3_5D0=564k5L3a5a0I5c5e5g5i0J5k5*5X0m5E5H5J525s021@0#1H0v0q0M0i305W5C0-5T025V5P5~1L0x0I0=3!4e5J5Q6a2~0=610b63655u5w695%6b5U6y2}6i6k5|5I6g5,600w620w640M0B0w1H0S6C3p6c6e2T6o6z5`0=0P0U6G6Z3i5-5/6P12140I165@6Y6I0m6W6U3W4K5d4Z4#5^6p6c0l5$6*022Q2N0v2k743p540L0P7b3P0y0S0=0u306Q7g530=5p6f5+0m7i0=0c4~50706!540U7r6?7t4V2i0D0w0A4P7A2}6_7N4T5N7o5n0=066(6@4(020s3r6`59020B6.2l7s5_0V0e4K5O7F5_4V5b5d6-132c6=2,6@545G6m6n5}7G5t0V5v7}2`7 7q7%5 676u7T5'027E2,6)7R7(6R2j8d5S6B7,6p4V0w8f0v4Y7`6/168h0-7d8E6q027^5:5h5j8H5o8r6J7)7{6:7;7~7t5{82838m7h4K4+8u6!4V6w892o8#3%6c000b0J056X8l6@8*875w5y0A5A8(7O7/021'0z8Q8I8f6N0q978:0h8?974V6s6u66687Q3P806(8!6H7t0S0G0=010C0r00010709050w5c0C0v2B0C8S8C2d8f5v1I0Y0C9i9a7z2T0E9q838`6r6L6t9a9k0b9c8t7=8v0=99649p9q9Z6K6M6O8+9)6d9g86889:8!9=9S6O6Q6S9`8^2`8.5 a48q8Za91L7Z2i0J648Va8a19#9j8f8O8c918na26v8|8,4F6p8Pas6{9?9$a38p6T4e184D0w2p2QaL4n1p4p2s2v2q0A1GaO0o4o0@aY0Y0!0$02.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)3=9xlTjwn8gv,S."5/:rCf7Fuemkdas p
h10itP(_y2[46cb]o 030z0w0J0A0I0b0B0C0S0b0A0B0B080m0J0I0D0m020E030B0v0x0x0A0q0N020k0V0b0v0/0V0f030o0_0{0}0 0@0D02031f181i0o1f0@0z0I0i0'0)0+0-0F0I0h0F0b1w0F0J0=030Z0T0b0w1r0*0,0m1v1x1z1x0J1F1H1D0J0q1g0J0F0'120B0D0A0f0-0O0m1J1t0m0s0#0w0f0A0x0w1D1$1'1,1L1/1H1=1@0=040C0K0q0V0D0V0B0I150f0C0X1!0q0q0w0S2c181`0f1g0o1Y2p1V1X1W1E0z1|0-1z0f1;291D1o1q0(1K2z0I2B0f0V2F1D0D2i1g2n2p2T0^1%2d2H1-2M0q0|0b0=0C0G2m2X0?2W1{2Z1L2#2%2(0O2+1'2-2n2y0m2=0A2'020C072_2o0@2|2:0-2 310C0Q352{2X2}3b2(0n3f373h392~0V2$302(0R3m2.2Y1s2;3r2?320t3w383z3a3B3t320g3F3o3H3q3s3c093N2/3P3j020G0H3U3y2I3Q3C0G2*192,3n3V3%3X0G2^3+2`3-3$2!3J310G343?363x3i3{0=0G3e3 3g3.3`3R443l473^424b3Y3v471j2R182F2s0z1X2x3p0S2N1^1g4o1h4m2V4k4u0X2S3O3%0y0f0=0I0x280q0J3f0C413p0f4J022b0w4O0V1#3m4f3p0y0=0X0s4Q4S3W0s0=0B0A0S0M0A0M0z290M0T0q140w3f4-3%0;020L513G3/0=1z0B0J0w0M0V0T0d0Y0B574G1-540j4,582!0=280I0z0B0M0|0a5l491L54060p3m0C5I4R5r2;0=17475K5m1L0V0=085q5R3a0T5a1;5B3_5D0=564k5L3a5a0I5c5e5g5i0J5k5*5X0m5E5H5J525s021@0#1H0v0q0M0i305W5C0-5T025V5P5~1L0x0I0=3!4e5J5Q6a2~0=610b63655u5w695%6b5U6y2}6i6k5|5I6g5,600w620w640M0B0w1H0S6C3p6c6e2T6o6z5`0=0P0U6G6Z3i5-5/6P12140I165@6Y6I0m6W6U3W4K5d4Z4#5^6p6c0l5$6*022Q2N0v2k743p540L0P7b3P0y0S0=0u306Q7g530=5p6f5+0m7i0=0c4~50706!540U7r6?7t4V2i0D0w0A4P7A2}6_7N4T5N7o5n0=066(6@4(020s3r6`59020B6.2l7s5_0V0e4K5O7F5_4V5b5d6-132c6=2,6@545G6m6n5}7G5t0V5v7}2`7 7q7%5 676u7T5'027E2,6)7R7(6R2j8d5S6B7,6p4V0w8f0v4Y7`6/168h0-7d8E6q027^5:5h5j8H5o8r6J7)7{6:7;7~7t5{82838m7h4K4+8u6!4V6w892o8#3%6c000b0J056X8l6@8*875w5y0A5A8(7O7/021'0z8Q8I8f6N0q978:0h8?974V6s6u66687Q3P806(8!6H7t0S0G0=010C0r00010709050w5c0C0v2B0C8S8C2d8f5v1I0Y0C9i9a7z2T0E9q838`6r6L6t9a9k0b9c8t7=8v0=99649p9q9Z6K6M6O8+9)6d9g86889:8!9=9S6O6Q6S9`8^2`8.5 a48q8Za91L7Z2i0J648Va8a19#9j8f8O8c918na26v8|8,4F6p8Pas6{9?9$a38p6T4e184D0w2p2QaL4n1p4p2s2v2q0A1GaO0o4o0@aY0Y0!0$02.
L'algorithme glouton
Le temps de calcul avec la méthode par force brute devient très rapidement trop long. C'est pour cela qu'on utilise un algorithme glouton.
On construit une liste de t-uplets (rentabilité, poids, valeur, nom) et on la classe dans l'ordre décroissant. On parcourt ensuite cette liste en regardant objet par objet s'il est possible de le prendre ou pas.
Exercice 5
Compléter la fonction sac_a_dos_glouton qui prend en paramètres une liste de dictionnaires liste_objets et un entier poids_max, et qui renvoie une solution obtenue avec l'algorithme glouton.
Cette fonction est bien plus rapide que la méthode par force brute, mais ne donne pas forcément la meilleure solution :
Exemple d'utilisation
>>> sac_a_dos_glouton(objets, 15)
(11, 11, ['Objet 1', 'Objet 3'])
La valeur obtenue est moins bonne qu'avec l'autre méthode, mais n'en est pas très loin.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)3=9x+lwjqnT8gv,S."5/:rf7uOemkdas p
h10itP(_y2[46cb]-o 030A0x0K0B0J0c0C0D0T0c0B0C0C080o0K0J0E0o020F030C0v0y0y0B0s0O020m0X0c0v0;0X0g030q0{0}0 110_0E02031h1a1k0q1h0_0A0J0k0)0+0-0/0G0J0j0G0c1y0G0K0@030#0U0c0x1t0,0.0o1x1z1B1z0K1H1J1F0K0s1i0K0G0)140C0E0B0g0/0P0o1L1v0o0t0%0x0g0B0y0x1F1'1)1.1N1;1J1@1_0@040D0L0s0X0E0X0C0J170g0D0Z1$0s0s0x0T2e1a1|0g1i0q1!2r1X1Z1Y1G0A1~0/1B0g1?2b1F1q1s0*1M2B0J2D0g0X2H1F0E2k1i2p2r2V0`1(2f2J1/2O0s0~0c0@0D0H2o2Z0^2Y1}2#1N2%2(2*0P2-1)2/2p2A0o2@0B2)020D072{2q0_2~2=0/31330D0R372}2Z2 3d2*0p3h393j3b300X2'322*0S3o2:2!1u2?3t2^340u3y3a3B3c3D3v340i3H3q3J3s3u3e093P2;3R3l020H0I3W3A2K3S3E0H2,1b2.3p3X3(3Z0H2`3-2|3/3'2$3L330H363^383z3k3}0@0H3g413i3:3|3T463n493`444d3!3x4g433r3=3G4m3I3;453!3O491l2T1a2H2u0A1Z2z3r0T2P1`1i4B1j4z2X4x4H0Z2U3Q3(0z0@0Z0t3h0D4n3Y0t0@0C0B0T0N0B0N0A2b0N0j0c0X16183h4#3(0?020M4_4s2$0@1B0C0K0x0N0X0U0e0!0C4 4T1/4|0l4Z4`51022a0J0A0C0N0~0a5d4b1N4|060r3o0D5A4!502?520J54562k0g1H0%2d0x5i5D0/0X0@085P5e5v0@0Q0V5z5B5j5E5l0X5n5p2k541)0K5V5u5R5T5:3{5'5m5o5q0B5s4g5B5C5W0/4V020t3t5@3k0@585a5/49615;0o0X0d0@2M684o5F5H57595b5t5^0/4|5y5 605$5Q300@0k326m3R5S025U6e5%3c6a6r6d2X6B4|0Q6t2 0C1,02000f0v0X0K056E1J0v0s6!6$6'6V3r4|5!6y6z6f6u6C5(5*6G3(6I6K2V6_69026b0!6:3R6T783(6X0@6-6%055`0C7f6/4x6S0@6?2V0F6^5A6M6{2O0y6~1/707y5'766Q2.7u7a7m620o7d6Z6#7g7w7k057b5f7o5#6^7u0g6o550N5J5L1B557S1N6I0n7)6N020B0E0E1?0A7-0o4|0M4~7I6g7Y026)7^6I0q7^7 7i7^5g7B7.877}6`896L6B7 818d2 8f727X0@7w880@06067V734G0H0@010D0w2f1X0J1K0A0v0D0E150(7$0B1I1K0B8I0y5)0g8M1?1U1K5$6@8w3Y7Z5I8X8O5M7(8k3r7+854'3t7E2|7G0@7|6R7J7 2k0k0x0s0C5O8-6H5?944U0T0@0h0s0v938{6g5w8v8o756P5p2S5G8a6h968n7n025Z9i8h6D320x6+0N0K6%9z9p7A8g7J0y0J0@3$8#7u64660s9p8}8)0U8+9e7F9t5h9I7~0@8c9f8e0@9#9s8|9y0c8r029,2.8$3;8p0X7x9$6`6i6k199}74537!8N9W7'9Y8@9t6x7q7s9^1/640J4Ya26n6|5o9G7e0c6'719@9j7i7#0x5-5K9;ac3.ae609j7D9m0s9o977z0@7,aK5'7:7=0g7@aO6v8_8:028qaU7_8s8vaeau5)5{5,0#azak956J9T9'a)5+axa,8?2qaf7*0@0Wa;am5c8#a'9x809z9B9D0#1Jaoa:a.9_b66*0s9C9EbbbeaL020bb08jad6A7J642k0K6+a19-9%bg9Abib99Fa!8matb5av5r82a~aXava+5.9;9?2|a|7.aG0N9nb27q1a4Q0x2r2Sb(4A1r4C2u2x2s8O1J2r4B0_0q0Z0#0%0C02.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)3=9x+lwjqnT8gv,S."5/:rf7uOemkdas p
h10itP(_y2[46cb]-o 030A0x0K0B0J0c0C0D0T0c0B0C0C080o0K0J0E0o020F030C0v0y0y0B0s0O020m0X0c0v0;0X0g030q0{0}0 110_0E02031h1a1k0q1h0_0A0J0k0)0+0-0/0G0J0j0G0c1y0G0K0@030#0U0c0x1t0,0.0o1x1z1B1z0K1H1J1F0K0s1i0K0G0)140C0E0B0g0/0P0o1L1v0o0t0%0x0g0B0y0x1F1'1)1.1N1;1J1@1_0@040D0L0s0X0E0X0C0J170g0D0Z1$0s0s0x0T2e1a1|0g1i0q1!2r1X1Z1Y1G0A1~0/1B0g1?2b1F1q1s0*1M2B0J2D0g0X2H1F0E2k1i2p2r2V0`1(2f2J1/2O0s0~0c0@0D0H2o2Z0^2Y1}2#1N2%2(2*0P2-1)2/2p2A0o2@0B2)020D072{2q0_2~2=0/31330D0R372}2Z2 3d2*0p3h393j3b300X2'322*0S3o2:2!1u2?3t2^340u3y3a3B3c3D3v340i3H3q3J3s3u3e093P2;3R3l020H0I3W3A2K3S3E0H2,1b2.3p3X3(3Z0H2`3-2|3/3'2$3L330H363^383z3k3}0@0H3g413i3:3|3T463n493`444d3!3x4g433r3=3G4m3I3;453!3O491l2T1a2H2u0A1Z2z3r0T2P1`1i4B1j4z2X4x4H0Z2U3Q3(0z0@0Z0t3h0D4n3Y0t0@0C0B0T0N0B0N0A2b0N0j0c0X16183h4#3(0?020M4_4s2$0@1B0C0K0x0N0X0U0e0!0C4 4T1/4|0l4Z4`51022a0J0A0C0N0~0a5d4b1N4|060r3o0D5A4!502?520J54562k0g1H0%2d0x5i5D0/0X0@085P5e5v0@0Q0V5z5B5j5E5l0X5n5p2k541)0K5V5u5R5T5:3{5'5m5o5q0B5s4g5B5C5W0/4V020t3t5@3k0@585a5/49615;0o0X0d0@2M684o5F5H57595b5t5^0/4|5y5 605$5Q300@0k326m3R5S025U6e5%3c6a6r6d2X6B4|0Q6t2 0C1,02000f0v0X0K056E1J0v0s6!6$6'6V3r4|5!6y6z6f6u6C5(5*6G3(6I6K2V6_69026b0!6:3R6T783(6X0@6-6%055`0C7f6/4x6S0@6?2V0F6^5A6M6{2O0y6~1/707y5'766Q2.7u7a7m620o7d6Z6#7g7w7k057b5f7o5#6^7u0g6o550N5J5L1B557S1N6I0n7)6N020B0E0E1?0A7-0o4|0M4~7I6g7Y026)7^6I0q7^7 7i7^5g7B7.877}6`896L6B7 818d2 8f727X0@7w880@06067V734G0H0@010D0w2f1X0J1K0A0v0D0E150(7$0B1I1K0B8I0y5)0g8M1?1U1K5$6@8w3Y7Z5I8X8O5M7(8k3r7+854'3t7E2|7G0@7|6R7J7 2k0k0x0s0C5O8-6H5?944U0T0@0h0s0v938{6g5w8v8o756P5p2S5G8a6h968n7n025Z9i8h6D320x6+0N0K6%9z9p7A8g7J0y0J0@3$8#7u64660s9p8}8)0U8+9e7F9t5h9I7~0@8c9f8e0@9#9s8|9y0c8r029,2.8$3;8p0X7x9$6`6i6k199}74537!8N9W7'9Y8@9t6x7q7s9^1/640J4Ya26n6|5o9G7e0c6'719@9j7i7#0x5-5K9;ac3.ae609j7D9m0s9o977z0@7,aK5'7:7=0g7@aO6v8_8:028qaU7_8s8vaeau5)5{5,0#azak956J9T9'a)5+axa,8?2qaf7*0@0Wa;am5c8#a'9x809z9B9D0#1Jaoa:a.9_b66*0s9C9EbbbeaL020bb08jad6A7J642k0K6+a19-9%bg9Abib99Fa!8matb5av5r82a~aXava+5.9;9?2|a|7.aG0N9nb27q1a4Q0x2r2Sb(4A1r4C2u2x2s8O1J2r4B0_0q0Z0#0%0C02.
Exercice 6
Comparer les résultats trouvés par les deux méthodes sur cette liste d'objets, avec un poids maximum de 10 :
objets = [{"nom": "Objet 1", "valeur": 80, "poids": 1},
{"nom": "Objet 2", "valeur": 100, "poids": 10}]
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
Expliquer les différences observées.
Explication
L'objet 1 est plus rentable que l'objet 2. L'algorithme glouton va donc le prendre, empèchant de prendre l'autre objet. Pourtant, l'autre objet, moins rentable mais bien plus lourd donne une meilleure solution.
Comparaison des deux algorithmes
Afin de tester les deux méthodes, nous allons générer des listes d'objets au hasard.
On fixera à l'avance des poids min et max, ainsi que des valeurs min et max.
Exercice 7
Compléter la fonction ci-dessous qui permet de générer au hasard une liste d'objets en indiquant les valeurs minimales et maximales ainsi que les poids minimums et maximums.
On rappelle que la fonction random.randint(a, b) renvoie une valeur entière comprise entre a et b inclus.
Exemples d'utilisation
>>> genere_liste_objets(4, 100, 400, 1, 10)
[{'nom': 'Objet 1', 'valeur': 301, 'poids': 7},
{'nom': 'Objet 2', 'valeur': 292, 'poids': 2},
{'nom': 'Objet 3', 'valeur': 303, 'poids': 1},
{'nom': 'Objet 4', 'valeur': 385, 'poids': 8}]
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)3=9x+lwjqn8gv,S."5/:rf7uOemkdas p
h10itP(_y2[46cb]o 030z0w0J0A0I0c0B0C0S0c0A0B0B080n0J0I0D0n020E030B0u0x0x0A0r0N020l0V0c0u0/0V0g030p0_0{0}0 0@0D02031f181i0p1f0@0z0I0j0'0)0+0-0F0I0i0F0c1w0F0J0=030Z0T0c0w1r0*0,0n1v1x1z1x0J1F1H1D0J0r1g0J0F0'120B0D0A0g0-0O0n1J1t0n0s0#0w0g0A0x0w1D1$1'1,1L1/1H1=1@0=040C0K0r0V0D0V0B0I150g0C0X1!0r0r0w0S2c181`0g1g0p1Y2p1V1X1W1E0z1|0-1z0g1;291D1o1q0(1K2z0I2B0g0V2F1D0D2i1g2n2p2T0^1%2d2H1-2M0r0|0c0=0C0G2m2X0?2W1{2Z1L2#2%2(0O2+1'2-2n2y0n2=0A2'020C072_2o0@2|2:0-2 310C0Q352{2X2}3b2(0o3f373h392~0V2$302(0R3m2.2Y1s2;3r2?320t3w383z3a3B3t320h3F3o3H3q3s3c093N2/3P3j020G0H3U3y2I3Q3C0G2*192,1j2R182F2s0z1X2x3p0S2N1^1g3:1h3.2V3+2`033_0X2S3O3%0y0g0=0I0x280r0J3f0C3x3i4a020r1'0z0V0x3m3n3V480=0X0s4h4j3p0g0s0=0i1;0w2i0M1z0B0J0w0M0V0T0e0Y0B3f4A3P0;020L4U3G3%4l0g0T4O4Q4S4!471-4X0k4z4#2!0=0j300M0x2K4,4u4.0=4:412o4i4=2;4@4_0|0a4}3$4 02512T544-5602280I0z0B4`4|52464~1L4/4;5i3a0=5l5n4`0A5a5r4V3%4X060q3m0C5M5h5t5y024K4M4)4R0J4T5r5O5c1L0V0=085w5P0n4X0P0U5L5N5G1-0y0=0s3r5(5!5Q0I5_2}0V0d4b175Y5:2;0T0=4n0g4F5b2}4X4Z5F555Q4'5U4+6f5x5*0=5J5.5N5/6g2~0=4P5V5}3p5$025'636t4'4w0I2k6b3p6d066q6r5Z3i6v4*4g6l5)5+6J3P0B1*02000f0u0V0J052M0x6$6'6)6X5H0=5-6D6m6A6C5g640-6Z0=6-6(050v6S0C706/6@5)6A0b6y3W66024L0r6:5d6e2V6E4b7i5#0=7b6U5`0n4{0=3*7l6m5I6N6r6|6u026w0Y7o0-6W7s2}6~6#6%714^1H0u0r76057I6n026?6{6t6_7c4$674o4q7X6A0m7X4l681o0g6T7y6V0=7k3,7m027R5p627^7t5v787t4l7 597X7A5r0E6O6s6m4l7G7@7|7z0=0P7X7N7V5A0B7V8a6=7'1-7%856Q4m7*4r7L6z0=7.8E3W7)0g7=8j426t6d7/5z0V5m5o4{818k7_5e8w5j8r5C5E826c6o7B8f5)4l5S4N8i5X8)8F028H8@8J020A0D0D1;0z8u4Y8R7F6S936M8c7C6t5=4m0Y7T8X2`6P4B0=8:6j5W3w0p440w2p2Q9s3/1p3;2s2v2q0A1G9v0p3:0@9F0Y0!0$02.
Exercice 8
Générer des listes d'objets au hasard et comparer les résultats obtenus par les deux méthodes.
Attention à ne pas utiliser des listes de longueurs supérieur à 20 pour la méthode par force brute.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
Exercice 9
Tester l'algorithme glouton avec des listes de centaines ou de milliers d'objets, pour voir l'efficacité au niveau du temps de calcul.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
# Tests(insensible à la casse)(Ctrl+I)