Problème du sac à dos et programmation dynamique

Présentation⚓︎

Le problème du sac à dos est un problème classique d'optimisation combinatoire. Il consiste à choisir des objets parmi une liste, chacun ayant un poids et une valeur, de manière à maximiser la valeur totale tout en respectant une contrainte de poids maximale.

Ce problème peut être résolu efficacement à l'aide de la programmation dynamique, une approche algorithmique qui consiste à décomposer un problème en sous-problèmes et à stocker leurs résultats intermédiaires pour éviter les redondances.

Énoncé⚓︎

On dispose de n objets, chacun ayant une valeur val[i] et un poids wt[i]. On souhaite les placer dans un sac à dos de capacité maximale W, de manière à maximiser la somme des valeurs sans dépasser la capacité.

Exemple de données⚓︎

Python
val = [50, 100, 150, 200]
wt = [8, 16, 32, 40]
W = 64

Résolution avec un algorithme glouton⚓︎

Le principe de l'algorithme glouton est de prendre à chaque itération l'objet non encore pris qui a le ratio valeur / poids le plus élevé possible.

Pour cela, on commence par trier les objets selon ce ratio décroissant. On crée une nouvelle liste ratio, que l'on va trier (par un tri par insertion). En parallèle de chaque permutation du tri par insertion, on permute les mêmes éléments des listes.

Remarque : il est bien sûr possible d'optimiser l'étape de tri en utilisant un tri en $\mathcal{O}(n \times \log(n))$.

Complète le code suivant :

Évaluations restantes : 5/5

.128013oP;f 8lkg5:j+,bry2a1éh3tvwT=u6e[(SWn9]x_s-c)7iqm/4p0d050#0F0y0t0U0h0P0f0R0h0t0P0P0C010y0U0Z010406050P0D0W0W0t0q0r040I0b0h0D0_0b0K050X101214160~0Z04051m1f1p0X1m0~0#0U0z0.0:0=0@0:0K0j0D0t0j0F0Q0Z0r0y0w1d0f0w0U0j0w0h1R0w0y0|050)0p0h0F1y0;0?011Q1S1U1S0y1!1$1Y0y0q1n1M0.190P0Z0t0K0@0s011(1A010e0+0F0K0t0W0F1Y1}1 241*271$2a2c0|0a0f0c0q0b0Z0b0P0U1c0K0f0%1{0q0q0F0R2x1f2f0K1n0X1M2K1@1_1^1Z0#2h1B0U0K292u1Y1v1x0/1)2U2W0K0b2!1Y0Z2D1n2I2K2;0 1~2y2$252*0q130h1Y0t1P2D0e0@030O0O0R2+0F1U2)0b0Q0u3f0|0f0u1f0t2=2^0}2@2g2`1*2|2~30320F340136383a3c2X3f0Q22040f0s3l3n1 3p2I2T013u0t2 1n310w333537390%3E2*3G0x3i0x3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0Y3i0Y3.1g3:3q2_1z3t0b2}3U3w3Y3y3!3C3%403)3g0k3i0k462;3;2^3R3^4g3|3B3$3b4m3e3g0E3i0E4s483=4b3@4d3v3W3x3z4A3 3d3G0T3i0T4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0g3i0g4!2J4$4a2%4)4e3_3{4i3}4k4C4;0Q0L3i0L4_3P4v3?4~4P3`4R4j4B3(4E3f0!0|0u0!5b4{4w4*505i535k4D3G0u0u5p3k0X3m3/4#495u4 4y524T4:413f3I0u3L5G3N4`5K5e4x4,4z4/555R0u3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560u4G5-4I6c4t5:626h5$5O5(673g0u4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560s5o046;5/6f4c6,645^5Q6Z0s5D6?5F5H6d6)4%6U5g6|5y6Y5m0s3I7e5b1q2/1f2!2N0#1_2S5e4B2Z1w1n2.0F2:3o5 1n4B7x2g0U0#0@372I5B3w7E7G6/5*232l0F7M6k7O2K5H6_0@0i0|0%0e7z6s250A3i7%7X3S0e0|0i2a0Z0P0t0R0i0O0j2D0F0#0r7,6*1*0{040H81772{0|0J874|25840o8c4w0|0A0y8h5e8f7z0f7(3t0|0z3U8m4(840S0l7z0~757C2y7L017H2^3G3I5h8G6x6M3H7P2b7R8H7N6 1Y5W0f8Z8q7-0K0|1e8D8#820@0b0|0C8p8r3@0p0|2k8w4}84868D8=3S8t8v8~7-8y8B8h8N0O7I3g5,8M7F8U7T6Z3+0f7Q7S7c3*8X3m8!8+888s040q0t1c8;7-8.048:8*8 840G8`89048u0h9H830|9G938,90040U9M0@840M9V019A0X9Z8%048k9Z9F9%0|9U9Q9s9W0|9Y9D7-7Z040e4d9y9R9(9/2;9r8d1*0b7*9T8)a28 0K8@9u1 1H9+0|8}2?8$8(ah040S9@6r9:8F9e8I1 3G5{9d9l6~5m439j8SaA5)6Zay8Y8!8 0R71030f0B0q0U0f1~0q0f2V0P0F0q2x2z0F0-9v1c0-2.0U0N1s0b7E0-0#0v0R2r0U0=1 8l8D8Cak4v989a0Q69az9f9m4o8R2caG6yb59o3JaL9_0|9|0q9~9;9Sa13oa33Ra69.a9brabad9v1D0Fanaj7y7-0W0U5pan8g9^9 amas3R8y8Aa 97au998J4F7KbV9g5m4GaEbcb8aB3G6n3M9q9qab0|0mbna48-8/b@8i9T96bPb3bX0Q6Bb78O564Xb(8Tc55Rc3aKb/bs5e9`0A1Q1$b{5!b=cl4(9A020j0y0dco4}bH0|5rbMbobu041 0#cv9Ia*0U0ban9Pb1bo9(b?bP8n9?cGa50|crctcU3@0|cIcKcR8x9O9-04cQaa9z0|0QcZ01cx5-an0MbSarcNat7Mb46Oc48V5m4?c8bd8Pd1cdcebi9R9`blc=9(9LcAb^9!a72Vc=9,c(62c#9wcJbKdg8ja~c}bQ0|bLc.bN9J92dzcS04c`b~dzc0aw3g6#d2b#3G58d6b*aH5mdQdadbb/b;04didHc)04cMbFdEc-d.bo9XdCd;dkdhcLc+d:3Ocfcpc:c=c@5Fd*8{cTdjbtb`e8cmd(d{dq9Id}2Jd 4}9Ac;eb4(e3c_d@d~d%d)d^dAd,d|c_dLevdN0K5B6=dRb95nbbc9d3eEbgd#b:alc,c=el9CdDboepbTb bVb45CbZd76l5DdVca6Ze$7V3peZc c15Ue%dWbee@e+eL6z8Lda8 de9}endredf425cCdnf79Nexef9tc$dvfbc!9)dyevdIereid%9Kc_c{48e;8Ue#9c3198dS6z9i9ke_8P5+eNdbby0|a-0Kfl3O9Eaic+eufP940|0SeAfUb2e!e?ayfzb!eH0uaDfEe,5mf+fI8ZaMaOaU2D0K0#0-1$0-0v0h0v2cfNf|a(aU1a0-2V0y0v2Da|g30f0)fN0f0V0D1%1$aUa;f{0f130N2z0D0f7@0R0fgm0Za!2cfO5YfvaveD6zb6f(e(5*4pe|fB3fb6f0eQ0y0b0)0h0O0A0F1VgD3J8 9AeUbxbGbI04czc|eBf#dO3fb-gKfF6lb%f-e}g@f;ej9IgUgW0O9KgkeSeaeVdkc@g/fudMg=gH3fc3g_f.5Bc7g}gP6Ah0d%bqesc/9Be2g-hd5JgFbWg?0ud1hkg~hEeJgLe-d99pdcbochcjbCfi9Sh33UgYg!1/h8040nc+9*fe9=fde59Iht2JfQdJh!020hctg*hudE8bhTcCcEdwb}h}cWh@cuhTac8^29bDc+frh)01bRfYh/3QeC5BdQhGhpdUhof*dZhNced%hVgXgZg#h!0nh_fpeQh(h,fcd-fZcO9.ezeYhfe=g?6;e^hl3giQgOeHiQe/d#iugVhWh6hShae9h#iBg%eQiciFh*iHihdEh.8Eewaqheg;iOhh70iRg~j0iVb+iT71b.fJeQi^h1cVi+hxbJiMi}fwc17ej1gPjlj4dX8Ke isjc7Yc#0(0D0qbwh`iJ04ivh53Uh78*b07y0X7B7i7w7k7t1f0y7njR2Q2L0t1#jO0X7l8C0%0)0+0P04.

Cette instance du problème donne une solution optimale, mais ce n'est pas toujours le cas. Essaie de trouver une autre instance pour laquelle l'algorithme glouton ne donne pas la solution optimale.

Stratégie exhaustive⚓︎

Si l'on considère les objets emportés dans le sac à dos, ils forment un sous-ensemble de tous les objets disponibles.

Une solution au problème peut donc être apportée en essayant toutes les combinaisons qui donnent tous les sous-ensembles.

On peut coder un sous-ensemble de n objets comme un nombre binaire compris entre 0 et $2^n - 1$, où quand le i-ème bit (en partant de la gauche) vaut 1, le i-ème objet est intégré au sous-ensemble.

Une technique pour obtenir ces valeurs des bits peut être de reprendre les restes successifs des divisions euclidiennes par 2 (vu en première NSI).

Parmi tous ces sous-ensembles dont le poids total ne dépasse pas la capacité du sac à dos, on cherche la valeur maximale.

Complète le code suivant :

Évaluations restantes : 5/5

.128013oP;f 8lkg5:j+,bry2a1éhC3tvw=u6e[(*SWn9]x_s-c)%7iqm/4p0d050%0F0z0t0W0h0Q0f0S0h0t0Q0Q0C010z0W0#010406050Q0D0Y0Y0t0q0r040J0b0h0D0{0b0L050Z12141618100#04051o1h1r0Z1o100%0W0A0:0=0@0_0=0L0j0D0t0j0F0R0#0r0z0w1f0f0w0W0j0w0h1T0w0z0~050+0p0h0F1A0?0^011S1U1W1U0z1$1(1!0z0q1p1O0:1b0Q0#0t0L0_0s011*1C010e0-0F0L0t0Y0F1!1 21261,291(2c2e0~0a0f0c0q0b0#0b0Q0W1e0L0f0)1}0q0q0F0S2z1h2h0L1p0Z1O2M1_1{1`1#0%2j1D0W0L2b2w1!1x1z0;1+2W2Y0L0b2$1!0#2F1p2K2M2?11202A2(272,0q150h1!0t1R2F0e0_030P0P0S2-0F1W2+0b0R0s0R0u0~0f0u1h0t2@2`0 2_2i2|1,2~3032340F3601383a3c3e2Z3h3h3l0s3o3q213s2K2V013x0t311p330w3537393b0)3H2,3J0y3l0y3N2J3r103R3v0_3U3W053Y3!3D3$3G2X3I3i0!3l0!3/1i3;3t2{1B3w0b2 3V3z3Z3B3#3F3(413*3i0k3l0k472?3=2`3S3_4h3}3E3%3d4n3g3i0E3l0E4t493?4c3^4e3y3X3A3C4B403f3J0V3l0V4K3P4v3u4N3T4P4g4R4i4T3 4m4W3i0g3l0g4#2L4%4b2)4*4f3`3|4j3~4l4D4=0R0M3l0M4`3Q4w3@4 4Q3{4S4k4C3)4F3j0$0~0u0$5c4|4x4+515j545l4E3J0u3k045D5t4a5v504z534U4;423j245F3M0Z3p3:4$5I5f4y4-4A4:565P0u3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622}5w5L665A570u4H5F4J6d4u5;636i5#5M5%683i0u4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3j595F5b6S616U6h6W6K6x6M570s5p046=5H6g4d6-655_5O6!0s5E716_6+6{5h6}5z6Z5n0s5R7c744(6V775y5N5(705+0s5-5V6e2L1s2;1h2$2P0%1{2U5f4C2#1y1p2:0F2=3r601p4C7I2i0W0%0_392K5C3z7P7R6:5)252n0F7X6l7Z2M5V6`0_0i0~0)0e7K6t270B3l7=7,3T0e0~0i2c0#0Q0t0S0i0P0F0O0w0t0D0Q0{0A0F7`750_0}040H8g7g2}0~0K8m4}278j0o8r4x0~0B0z8w5f8u7K0f7?3w0~0A3V8B4)8j0T0l7K107r7N2A7W017S2`3J5R5i8V6y6N3K0f7#7%7a8Z1!5.0f8;8F7{0L0~1g8S8?8h010b0~0C8E8G3^0p0~2m8L4~8j8l8S933T8I8K9c7{8N8Q8w8$0P7T3i5+8#7Q8W7Y6!3,8*2d7$9t7(9v8/3p8=8|8n8H04150O0P8J1c8f8{9d8 04919Q7{0Y0W0~5s8S8R2^3R9m9o0R5|9r8,6 5n449x2e9.7l9:9D3s9h4w9)8Y4p7V9s8%574q9=9za35P6a3N9$7J9(a29n9 0R6o9-9A8-4G7!9y9@6zai9`9F9d7.040e4e928@0~0WaA8}0b7^042XaE9H940~0q211J988t0~9b9%8}9X0~5T2?9G8s1,9S0I0IaKa$3^8_aR1,8N8P9#9laf9*6Caka86!4Ya6aq8(a`8:9F8=9d8^040z0b0+0h9M3V0D9Pa!9R90a+3SaX049!6s9|7Oa^ah6Pa{9u5n4@a al9/3Jbub3b4a#8xb8ba3V0P0B0F1X8A9VaFbjbQaL01bmbo49bq8Ubs213J6$bv9B5n59bza|b+atbFbG5Z0~4Cbk5f9S9UbhaBaIb_4)0S5E030f1Q0S0w0F0qc71)1(0/0p2y0/2C0h000v0S0q2y0D2F2B1)4C0f2b0fcf2c0W2F9kbZ0f9~b$6A6?b)am5oao9?bA9^5CcHbEb4b60~0mc04~b{cW27bWcZ1,c20~c40mcD0L1x0Xbf0fcj2X1x0S1)ci0b0p0m0*cBaVbr7X9*5Da1b06m3kb-bw5C5E3Nb;b=c1c30f0x3V0S0D0.cr0/2F8c0F0/120Sc^0@0W0echcc332$0W2x1Q0F0D0;7P0W2b2Y0f200q0faZbYd0b!d2ah0u8!339mb*5C24d9d$6A8!cRau7{aw0B1S1(c$a-04b^bTa,8~0~020j0z0dd@bV9Ybna/8i0~a=bpdUcDb#0L5C9qd!afd*3j9w8+cNar5*b:de8;avaC7;d{bHd`b}bR040Ue3bmdS3P9d8jeadTad9}ee5C9,eid65{cLa7da6A9,d-eset7{c(04c41Q7Gc-c;00c{c}0z0fcVa?cCcEef6AaaeReo8(0ua5enb.69ere!b5b~b9bbbd9Oe39S0nb|3rdf639f0he7018j0Gfmb7e?ec8C0~0Nc eMd19td3aje}f36A4Hd)cJ6nf5f6fi8obIfabMbOfd0~ffe3b78zfmfofqcUfYfvfxeHaedWcF3ja`fDeWf-eUeS6!6BfKb;cTd_3cfS040Z0Zfg3PfM1,eFe3e%c42vcp122yc_ds2B1ydE0W1f0/dHdJ1xdMdsf(7sf*fAdXbuf/ek0ubyf2f:gzf_bFf{fsfhbi04fUex5fbm3ne@ece_5Cb(gxfIb,gBgyb(eZe#8}awdye39af!fObKfQ1;8Eg40_9S020he1g22Lg=9e048qgM4)aG0~210%fV0~f9bK9Nbff$048Ogr8Tedf+e`3hcHgVbB3i6=f=e~6;cQ9Ef6f{9Kfbhch1cXbSeAbUb7h9bchbbgeLf)eNhj8ZdchncOhpd8gYcJ719`achMfz8Xf,7cd5hs5Ph(fHho3hd,hvg$bUg80f292A2C0p0bdI1(cr0fb91dgfcddO2w2xcf1W0z0v0Qhg5IgShpehhih*7mhrfE3h9qcReu042F0zcp8`hEd|b7hyhJie0Z7M7t7H7v7E1h0z7yiJ2S2N0t1%iG0Z7w8R0)0+0-0Q04.

Quel est le principal inconvénient de cette stratégie ?

Stratégie de résolution (bottom-up)⚓︎

On crée une table table[i][j] où chaque cellule contient la valeur maximale atteignable avec les i premiers objets et un sac à dos de capacité j.

Attention : la première ligne i=0 est donc la ligne avec aucun objet, la deuxième ligne i=1 est donc la ligne avec le premier objet (indice 0). Il y a alors un décalage entre l'indice des lignes i et l'indice de l'objet i - 1.

La table est de taille (n+1) × (W+1). On la remplit progressivement selon les règles suivantes :

Si i == 0 ou j == 0, la valeur est 0 (aucun objet ou capacité nulle).
Pour la ligne d'indice i, soit on peut inclure l'objet i - 1 (wt[i - 1] <= j), on choisit entre :
- ne pas l'inclure, dans ce cas, on reprend la valeur sans l'objet : table[i-1][j]
- l'inclure : val[i - 1] + table[i - 1][j - wt[i - 1]]
Sinon, l'objet i ne peut pas être inclus et on reprend la valeur : table[i-1][j].

Compléte le code ci-dessous pour implémenter la solution :

Évaluations restantes : 5/5

.128013oèPf8gbr1a3tv=uàn9xsc)7qçR/p0dùI; lk5:j+,y2éChw6e[(SW]_im4-050E0X0m0k0(0J0u0I0v0J0k0u0u0o010m0(0C010406050u0p0)0)0k0i0Q040!0b0J0p0 0b0r050B16181a1c140C04051s1l1v0B1s140E0(0n0@0_0{0}0_0r0g0p0k0g0X0+0C0Q0m0U1j0I0U0(0g0U0J1X0U0m12050/0h0J0X1E0`0|011W1Y1!1Y0m1*1,1(0m0i1t1S0@1f0u0C0k0r0}0R011.1G010e0;0X0r0k0)0X1(23252a1:2d1,2g2i120a0I0d0i0b0C0b0u0(1i0r0I0-210i0i0X0v2D1l2l0r1t0B1S2Q1}1 1~1)0E2n1H0(0r2f2A1(1B1D0^1/2!2$0r0b2*1(0C2J1t2O2Q2`15242E2,2b2:0i190J1(0k1V2J0e0}030%0%0v2;0X1!2/0b0+0l0+0j120I0j1l0k2{2~132}2m301:323436380X3a013c3e3g3i2%3l0+28040I0R3s3u253w2O2Z013B0k351t370U393b3d3f0-3L2:3N0l3p0l3T2N3v143X3z0}3!3$053(3*3H3,3K2#3M3m0*3p0*3^1m3`3x2 1F3A0b333#3D3)3F3+3J3.473:3m0L3p0L4d2`3{2~3Y3 4n433I3-3h4t3k3m0W3p0W4z4f3|4i3~4k3C3%3E3G4H463j3N0x3p0x4Q3V4B3y4T3Z4V4m4X4o4Z454s4$3m0f3p0f4+2P4-4h2-4:4l40424p444r4J4{0+0s3p0s503W4C3}554W414Y4q4I3/4L3n0D120j0D5i524D4;575p5a5r4K3N0j3o045J5z4g5B564F594!4`483n3P0j3S0B3t3_4,5O5l4E4?4G4_5c5V0j3=5L3@5!3U515(4/5*5o4@5q4#5/4a5L4c5@5$5_4S545|584^5b5s5I4w5L4y654e5%68315C5R6c5G5d0j4N5L4P6j4A5`696o5+5S5-6e3m0j4(5L4*6x4R5k5{6B5}5,6d5H6G4}5L4 6L6l6N6A5Q6C6q604u3n5f5L5h6Y676!6n6$6Q6D6S5d0R5v046{5N6m4j6?6b5 5U6*0R5K776 6;715n735F6)5t0R3P7i7a4.6#7d5E5T5.765;0R5?5#6k6:7m6=7o5~7f757h620R647w6y704U727p6E6T3O6g0R6i7J6M7z7c4=6@6(7E3N0R6u7(7l537A7Z7e7q6F3O6I0R6K7V6Z7X7M7B6R6r5V0R6V817+5P7}6^7 766,0R6.7_2P1w2^1l2*2T0E1 2Y5l4I2)1C1t2@0X2_3v661t4I8u2m0(0E0}3d2O5I3D8B8D6_5/292r0X8J885t5K3^7L010K120-0e8w6z2b0V3p8!8U0r0e120K2g0C0u0k0v0K8)7b0}11040Z8^7{3Z120#8~7,1:8{0P8w0I8#3A120V0m933Y96989a3~120n3#9f5l8{0w0M8w147x8z2E8I018E2~7%8H8C9z8K768M2h8O9F8Q9C2Q5#8U8%3Q0I9T9o4/0u0E12019!9t9f9y9A253;9D8P7g9+0I8N9-7$3m5;8T8_019X3p9T2v0b0p0i0I0i0S0ua00E2J0I1,0I2@0b1+0c2i0P0I1U2J0)0C1!0m0I0p2E191}0(0v0Xai0E1jap0v0U0k0y0p1-0v0`1-2#1BaF0X9$9v5O9(0%8F499,9L9.aV9:9J9=7r5t629_8 9|9S9T0_0I9m1,a10I190t0(341-2z0{0(1+a|a0a2arac0b8B0?0N0I0.ba2 1T0(2B0{25ap24a21,0?0(acal0(0X0i0?ae0N0.0uaP2|3XaSaU0+6g5oaS9M4v9I2ia$7;bF5@9ubA4CbC9B4MaW7P5d4Na!bLaX9?0+6ua*940}a,9~0I0T000X0uapabalanbf8;1N0I2C0S0i0k0 0e0I0Z2i0)b68;2D0waibbab1!2f0?2f1}1-bm0@3h1gcm2Gaw1_1-at0iavaO9vbQ8vbB9E9)0r4%bW9G5t4(b!9KbX5V6Ib*3Yb-9~aFbo2f0I0eaAaq2E3#0g4k2C0U2i2Fa|2x0gc11o2D2F0Q2r0(aN99cz9%cDaTbU0+6VbGc~bId1bKcMcI3Nd2658UcS9T9!01bzcBbSc~bD6,d3bM7Q5fcLdp5ddn5@b.9j90041k9v998U0b120o9i8*0h122q9V548{8}aQ8*9l9ndR9`9qdi3VaRdld05xcHd5d%dsb$a%5I6|3TcAdZcC8JbD5Jd(aY3n3od+cN6*d_9Oa-dD9`0v5K030I0G0r2C0(3#bfbsaa371`1-2Gadc/2hat0(1U0Ec@2hc_aGdY8ed?9Fd^3Pdod,7;5Yd7dt5/eCdw9~dy0r12ejdI9`dF04dHdCdy8{0Y0YdN2b0)0(125yeW8U8W04cY0ieR8 eO040%e;b+010b9R2#e_4DdK04c11JcybR8 dPe#9b0492e+eS120Oe 5le%5wf98`120w0$fh4/e-e/fq6912e^fd8 e|12e~fye`0rf1f31Nfl01f8dVe=12dB2`e4fzfffue$e(5LfJ9qfpc|fM9xd#9*6G9^37bHd{5:eHeE7Qf/e2d;eydkd@d$a)f,d4f.4ad~d96Ga)eL9U8Ue612e80A0Xam1!bhb}2Ga/ejcd2 0b182f0zbi0I0qehc,0pa_agcl1X2$0IcU210raw0igBab0jegbv0.ex9wb~f(cF6GbFf~eIe04wg2d)bO3tdxe,12ftfD4DfBfU1:fA04fCfQeNfG25fIf$9g12dQf6e`fjfXg{9p1297h35{fOg.0}eTfgg+fifW3rh7dOfn9sf#g gQf{f)3nb)gVf;6sbZ9;hu5/b)bPc}hpgS3ncPhtd 8RcKhxhI5IcPg6b.fRe`fs4khadz0NhVg:g=3vhRf012fHf5djf7g}fJe?fcg?dEfThe4/h1hhhnh4049rgOd!hD5Id2hHg33n4}gZf.dbg$hQicdye-0(8Zh@fv04hXii2beT0oeVh;9`h1e*h{4/8{hl6yg{bThq0jdni4d)drhLi5iD1(hPiciddS04eQhi2beYh.g-iS95120$e!iX9kikfYiZhYdGhVithVg904e81@gB2#1h2e2F250?a/2i16a90b0Fgucvcx0I370S0m0Sb~eb0 ee0u0S1-0k0n2Kc,0?iu4fiAgR7%d/iFd{6{f:hM3mjwe2iNhQie124JihirfN049di)04i#ivij0(i+040+i-hgjMf!jIe`eT020J0m0Hiqh#eN12iljPiT12iyjphniBhE77d`b%j`i8j|8SiMjCeMiPgM2L0%0V0X1#9eimg/i,kci%jLi$fK12jOh+fEiWjZ3YeTjUkf01h_jXh ezcE7%eCjuj|28j~d-jzeKibk2jDiPiRj/iYjNiVg;jXkld=9`e?j.kmg|04jYj+h=eUhVfF12a^jMg~j?kZj^7%f+hohy7sjxi57uiLkJkKiNj,04a;jMkUf_jJjRktkrjVfkki8{k$3Vh$5lhck*eP0kb0l5kRl9kplj12kslsh^jWleiZl6gP5)j-jSlvk%kW12k50mk7k91^jXh6izj@jrjzf}k^jy3Og1iId57Hk~e3l0kLlIiQln1,lpkie?lrlHfSjTlch2kOfmk#lBl2kYkVh,k#kxf`eAd07Tj{kG7Rk{l#g#l(l0eXfnm48AlT3OhslWk|hwa#k_7hhAk jCjE043h0uh*m1e`ixmjf%i1jzhGmol#hKmrlX7@l%l)g%l+kNkZh|l~iPl=mCk!i!kRm0l7mDi*lakelwijmUm!mWlqlFl_h`mViwlAm%kwhmk;ml81m97;n2kFn4ia3wjqmH3OiEmKjviHmNk|dvk mx2J0ma1fPl?knl,lolzkQl:h9num$nwfbm~lR8v0B8y8f8t8h8q1l0m8knL2W2Rl-nI0B8i9u0-0/0;0u04.

Exécution avec les données d'exemple⚓︎

Python
val = [50, 100, 150, 200]
wt = [8, 16, 32, 40]
W = 64

Il est bien sûr possible de résoudre ce problème par une méthode récursive (top-down) avec mémoïsation.

Il est bien sûr possible de résoudre ce même problème avec une méthode récursive de haut en bas (Top-down).

Classe du problème du sac à dos avec seuil.⚓︎

Compte tenu de la grande taille que peut prendre la matrice avec des poids très différents (Exemple 35g, 4,738 kg, 120kg), répondre à la question : "Pour un sac à dos donné, existe-t-il une combinaison d'objets ayant au moins la valeur v ?"

est un problème de la classe NP.