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

.128013it3a;djv,nT2S5éwbcy+14q: f-up08W_)9eklohxrP=[s6(]/mg7050g0K0c0e0b0M0U0z0s0M0e0U0U0S010c0b0D010406050U0C0Z0Z0e0Q0t040n0N0M0C0_0N0k050Y101214160~0D04051m1f1p0Y1m0~0g0b0i0.0:0=0@0:0k0!0C0e0!0K0B0D0t0c0O1d0z0O0b0!0O0M1R0O0c0|050)0r0M0K1y0;0?011Q1S1U1S0c1!1$1Y0c0Q1n1M0.190U0D0e0k0@0m011(1A010A0+0K0k0e0Z0K1Y1}1 241*271$2a2c0|0a0z0R0Q0N0D0N0U0b1c0k0z0%1{0Q0Q0K0s2x1f2f0k1n0Y1M2K1@1_1^1Z0g2h1B0b0k292u1Y1v1x0/1)2U2W0k0N2!1Y0D2D1n2I2K2;0 1~2y2$252*0Q130M1Y0e1P2D0A0@030H0H0s2+0K1U2)0N0B0v3f0|0z0v1f0e2=2^0}2@2g2`1*2|2~30320K340136383a3c2X3f0B22040z0m3l3n1 3p2I2T013u0e2 1n310O333537390%3E2*3G0d3i0d3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0w3i0w3.1g3:3q2_1z3t0N2}3U3w3Y3y3!3C3%403)3g0o3i0o462;3;2^3R3^4g3|3B3$3b4m3e3g0V3i0V4s483=4b3@4d3v3W3x3z4A3 3d3G0#3i0#4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0F3i0F4!2J4$4a2%4)4e3_3{4i3}4k4C4;0B0J3i0J4_3P4v3?4~4P3`4R4j4B3(4E3f0E0|0v0E5b4{4w4*505i535k4D3G0v0v5p3k0Y3m3/4#495u4 4y524T4:413f3I0v3L5G3N4`5K5e4x4,4z4/555R0v3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560v4G5-4I6c4t5:626h5$5O5(673g0v4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560m5o046;5/6f4c6,645^5Q6Z0m5D6?5F5H6d6)4%6U5g6|5y6Y5m0m3I7e5b1q2/1f2!2N0g1_2S5e4B2Z1w1n2.0K2:3o5 1n4B7x2g0b0g0@372I5B3w7E7G6/5*232l0K7M6k7O2K5H6_0@0L0|0%0A7z6s250q3i7%7X3S0A0|0L2a0D0U0e0s0L0H0!2D0K0g0t7,6*1*0{040W81772{0|0G874|25840j8c4w0|0q0c8h5e8f7z0z7(3t0|0i3U8m4(840I0y7z0~757C2y7L017H2^3G3I5h8G6x6M3H7P2b7R8H7N6 1Y5W0z8Z8q7-0k0|1e8D8#820@0N0|0S8p8r3@0r0|2k8w4}84868D8=3S8t8v8~7-8y8B8h8N0H7I3g5,8M7F8U7T6Z3+0z7Q7S7c3*8X3m8!8+888s040Q0e1c8;7-8.048:8*8 840T8`89048u0M9H830|9G938,90040b9M0@840X9V019A0Y9Z8%048k9Z9F9%0|9U9Q9s9W0|9Y9D7-7Z040A4d9y9R9(9/2;9r8d1*0N7*9T8)a28 0k8@9u1 1H9+0|8}2?8$8(ah040I9@6r9:8F9e8I1 3G5{9d9l6~5m439j8SaA5)6Zay8Y8!8 0s71030z0l0Q0b0z1~0Q0z2V0U0K0Q2x2z0K0-9v1c0-2.0b0P1s0N7E0-0g0p0s2r0b0=1 8l8D8Cak4v989a0B69az9f9m4o8R2caG6yb59o3JaL9_0|9|0Q9~9;9Sa13oa33Ra69.a9brabad9v1D0Kanaj7y7-0Z0b5pan8g9^9 amas3R8y8Aa 97au998J4F7KbV9g5m4GaEbcb8aB3G6n3M9q9qab0|0hbna48-8/b@8i9T96bPb3bX0B6Bb78O564Xb(8Tc55Rc3aKb/bs5e9`0q1Q1$b{5!b=cl4(9A020!0c0fco4}bH0|5rbMbobu041 0gcv9Ia*0b0Nan9Pb1bo9(b?bP8n9?cGa50|crctcU3@0|cIcKcR8x9O9-04cQaa9z0|0BcZ01cx5-an0XbSarcNat7Mb46Oc48V5m4?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|0IeAfUb2e!e?ayfzb!eH0vaDfEe,5mf+fI8ZaMaOaU2D0k0g0-1$0-0p0M0p2cfNf|a(aU1a0-2V0c0p2Da|g30z0)fN0z0x0C1%1$aUa;f{0z130P2z0C0z7@0s0zgm0Da!2cfO5YfvaveD6zb6f(e(5*4pe|fB3fb6f0eQ0c0N0)0M0H0q0K1VgD3J8 9AeUbxbGbI04czc|eBf#dO3fb-gKfF6lb%f-e}g@f;ej9IgUgW0H9KgkeSeaeVdkc@g/fudMg=gH3fc3g_f.5Bc7g}gP6Ah0d%bqesc/9Be2g-hd5JgFbWg?0vd1hkg~hEeJgLe-d99pdcbochcjbCfi9Sh33UgYg!1/h8040uc+9*fe9=fde59Iht2JfQdJh!020Mctg*hudE8bhTcCcEdwb}h}cWh@cuhTac8^29bDc+frh)01bRfYh/3QeC5BdQhGhpdUhof*dZhNced%hVgXgZg#h!0uh_fpeQh(h,fcd-fZcO9.ezeYhfe=g?6;e^hl3giQgOeHiQe/d#iugVhWh6hShae9h#iBg%eQiciFh*iHihdEh.8Eewaqheg;iOhh70iRg~j0iVb+iT71b.fJeQi^h1cVi+hxbJiMi}fwc17ej1gPjlj4dX8Ke isjc7Yc#0(0C0Qbwh`iJ04ivh53Uh78*b07y0Y7B7i7w7k7t1f0c7njR2Q2L0e1#jO0Y7l8C0%0)0+0U04.

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

.128013Cit3a;djv,n2S5éwb*cy+14q: f-up08W_)9ekl%ohxrP=[s6(]/mg7050h0L0d0f0c0N0W0A0t0N0f0W0W0U010d0c0E010406050W0D0#0#0f0S0u040n0P0N0D0{0P0l050!12141618100E04051o1h1r0!1o100h0c0j0:0=0@0_0=0l0$0D0f0$0L0C0E0u0d0Q1f0A0Q0c0$0Q0N1T0Q0d0~050+0r0N0L1A0?0^011S1U1W1U0d1$1(1!0d0S1p1O0:1b0W0E0f0l0_0m011*1C010B0-0L0l0f0#0L1!1 21261,291(2c2e0~0a0A0T0S0P0E0P0W0c1e0l0A0)1}0S0S0L0t2z1h2h0l1p0!1O2M1_1{1`1#0h2j1D0c0l2b2w1!1x1z0;1+2W2Y0l0P2$1!0E2F1p2K2M2?11202A2(272,0S150N1!0f1R2F0B0_030I0I0t2-0L1W2+0P0C0m0C0w0~0A0w1h0f2@2`0 2_2i2|1,2~3032340L3601383a3c3e2Z3h3h3l0m3o3q213s2K2V013x0f311p330Q3537393b0)3H2,3J0e3l0e3N2J3r103R3v0_3U3W053Y3!3D3$3G2X3I3i0x3l0x3/1i3;3t2{1B3w0P2 3V3z3Z3B3#3F3(413*3i0o3l0o472?3=2`3S3_4h3}3E3%3d4n3g3i0X3l0X4t493?4c3^4e3y3X3A3C4B403f3J0%3l0%4K3P4v3u4N3T4P4g4R4i4T3 4m4W3i0G3l0G4#2L4%4b2)4*4f3`3|4j3~4l4D4=0C0K3l0K4`3Q4w3@4 4Q3{4S4k4C3)4F3j0F0~0w0F5c4|4x4+515j545l4E3J0w3k045D5t4a5v504z534U4;423j245F3M0!3p3:4$5I5f4y4-4A4:565P0w3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622}5w5L665A570w4H5F4J6d4u5;636i5#5M5%683i0w4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3j595F5b6S616U6h6W6K6x6M570m5p046=5H6g4d6-655_5O6!0m5E716_6+6{5h6}5z6Z5n0m5R7c744(6V775y5N5(705+0m5-5V6e2L1s2;1h2$2P0h1{2U5f4C2#1y1p2:0L2=3r601p4C7I2i0c0h0_392K5C3z7P7R6:5)252n0L7X6l7Z2M5V6`0_0M0~0)0B7K6t270q3l7=7,3T0B0~0M2c0E0W0f0t0M0I0L0R0Q0f0D0W0{0j0L7`750_0}040Y8g7g2}0~0H8m4}278j0k8r4x0~0q0d8w5f8u7K0A7?3w0~0j3V8B4)8j0J0z7K107r7N2A7W017S2`3J5R5i8V6y6N3K0A7#7%7a8Z1!5.0A8;8F7{0l0~1g8S8?8h010P0~0U8E8G3^0r0~2m8L4~8j8l8S933T8I8K9c7{8N8Q8w8$0I7T3i5+8#7Q8W7Y6!3,8*2d7$9t7(9v8/3p8=8|8n8H04150R0I8J1c8f8{9d8 04919Q7{0#0c0~5s8S8R2^3R9m9o0C5|9r8,6 5n449x2e9.7l9:9D3s9h4w9)8Y4p7V9s8%574q9=9za35P6a3N9$7J9(a29n9 0C6o9-9A8-4G7!9y9@6zai9`9F9d7.040B4e928@0~0caA8}0P7^042XaE9H940~0S211J988t0~9b9%8}9X0~5T2?9G8s1,9S0s0saKa$3^8_aR1,8N8P9#9laf9*6Caka86!4Ya6aq8(a`8:9F8=9d8^040d0P0+0N9M3V0D9Pa!9R90a+3SaX049!6s9|7Oa^ah6Pa{9u5n4@a al9/3Jbub3b4a#8xb8ba3V0I0q0L1X8A9VaFbjbQaL01bmbo49bq8Ubs213J6$bv9B5n59bza|b+atbFbG5Z0~4Cbk5f9S9UbhaBaIb_4)0t5E030A1Q0t0Q0L0Sc71)1(0/0r2y0/2C0N02030e0K0g0p0t0S2y0D2F2B1)4C0A2b0Acf2c0c2F9kbZ0A9~b$6A6?b)am5oao9?bA9^5CcLbEb4b60~0ic04~b{c!27bWc%1,c20~c40icH0l1x0ybf0Acjclcn2X1x0t1)ci0P0r0i0*cFaVbr7X9*5Da1b06m3kb-bw5C5E3Nb;b=c1c30A0b3V0t0D0.cv0/2F8c0L0/120tc~0@0c0Bchcc332$0c2x1Q0L0D0;7P0c2b2Y0A200S0AaZbYd6b!d8ah0w8!339mb*5C24dfd,6A8!cVau7{aw0q1S1(c*a-04b^bTa,8~0~020$0d0gd}bV9Ybna/8i0~a=bpd!cHb#0l5C9qd*afd:3j9w8+cRar5*b:dk8;avaC7;e1bHe0b}bR040Oe9bmdY3P9d8jegdZad9}ek5C9,eodc5{cPa7dg6A9,d?eyez7{c,04c41Q7Gc;c^ckcm0gd1d30d0AcZa?cGcIel6AaaeXeu8(0wa5etb.69exe*b5b~b9bbbd9Oe99S0vb|3rdl639f0Ned018j0Vfub7e~ei8C0~0Zd5eSd79td9ajf5fb6A4Hd/cN6nfdfefq8obIfibMbOfl0~fne9b78zfufwfycYf*fDfFeNaed$cJ3ja`fLe$f^e!eY6!6BfSb;cXd 3cf!040!0!fo3PfU1,eLe9e-c42vct122yc dy2B1ydK0c1f0/dNdP1xdSdyf:7sf=fId%buf`eq0wbyfaf{gHg1bFg3fAfpbi04f$eD5fbm3ne eif15Cb(gFfQb,gJgGb(e)e+8}awdEe99af,fWbKfY1;8Egc0_9S020Ne7ga2Lg}9e048qgU4)aG0~210hf%0~fhbK9Nbff.048Ogz8Tejf?f23hcLg%bB3i6=f}f66;cU9Efeg39Kfjhkh9c#bSeGbUb7hhbchjbgeRf;eThr8ZdihvcShxdeg*cN719`achUfH8Xf@7cdbhA5Ph:fPhw3hd=hDg.bUgg0A292A2C0r0PdO1(cv0Ab91dgncddU2w2xcf1W0d0p0Who5Ig!hxenhqh=7mhzfM3h9qcVeA042F0dct8`hMe2b7hGhRim0!7M7t7H7v7E1h0d7yiR2S2N0f1%iO0!7w8R0)0+0-0W04.

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

.128013ita;,n2R7+14 fIjW08elor=[à]/ùmC3dvS5éwbçcyq:-up)_9hxPès6(gk050H0u0c0d0b0v0%0n0P0v0d0%0%0y010c0b0V010406050%0U0E0E0d0x0Q040J0w0v0U0 0w0g050C16181a1c140V04051s1l1v0C1s140H0b0I0@0_0{0}0_0g0*0U0d0*0u0T0V0Q0c0Z1j0n0Z0b0*0Z0v1X0Z0c12050/0N0v0u1E0`0|011W1Y1!1Y0c1*1,1(0c0x1t1S0@1f0%0V0d0g0}0h011.1G010o0;0u0g0d0E0u1(23252a1:2d1,2g2i120a0n0#0x0w0V0w0%0b1i0g0n0-210x0x0u0P2D1l2l0g1t0C1S2Q1}1 1~1)0H2n1H0b0g2f2A1(1B1D0^1/2!2$0g0w2*1(0V2J1t2O2Q2`15242E2,2b2:0x190v1(0d1V2J0o0}030X0X0P2;0u1!2/0w0T0G0T0l120n0l1l0d2{2~132}2m301:323436380u3a013c3e3g3i2%3l0T28040n0h3s3u253w2O2Z013B0d351t370Z393b3d3f0-3L2:3N0G3p0G3T2N3v143X3z0}3!3$053(3*3H3,3K2#3M3m0m3p0m3^1m3`3x2 1F3A0w333#3D3)3F3+3J3.473:3m0K3p0K4d2`3{2~3Y3 4n433I3-3h4t3k3m0(3p0(4z4f3|4i3~4k3C3%3E3G4H463j3N0j3p0j4Q3V4B3y4T3Z4V4m4X4o4Z454s4$3m0t3p0t4+2P4-4h2-4:4l40424p444r4J4{0T0Y3p0Y503W4C3}554W414Y4q4I3/4L3n0s120l0s5i524D4;575p5a5r4K3N0l3o045J5z4g5B564F594!4`483n3P0l3S0C3t3_4,5O5l4E4?4G4_5c5V0l3=5L3@5!3U515(4/5*5o4@5q4#5/4a5L4c5@5$5_4S545|584^5b5s5I4w5L4y654e5%68315C5R6c5G5d0l4N5L4P6j4A5`696o5+5S5-6e3m0l4(5L4*6x4R5k5{6B5}5,6d5H6G4}5L4 6L6l6N6A5Q6C6q604u3n5f5L5h6Y676!6n6$6Q6D6S5d0h5v046{5N6m4j6?6b5 5U6*0h5K776 6;715n735F6)5t0h3P7i7a4.6#7d5E5T5.765;0h5?5#6k6:7m6=7o5~7f757h620h647w6y704U727p6E6T3O6g0h6i7J6M7z7c4=6@6(7E3N0h6u7(7l537A7Z7e7q6F3O6I0h6K7V6Z7X7M7B6R6r5V0h6V817+5P7}6^7 766,0h6.7_2P1w2^1l2*2T0H1 2Y5l4I2)1C1t2@0u2_3v661t4I8u2m0b0H0}3d2O5I3D8B8D6_5/292r0u8J885t5K3^7L010+120-0o8w6z2b0M3p8!8U0g0o120+2g0V0%0d0P0+8)7b0}11040)8^7{3Z120r8~7,1:8{0f8w0n8#3A120M0c933Y96989a3~120I3#9f5l8{0W0S8w147x8z2E8I018E2~7%8H8C9z8K768M2h8O9F8Q9C2Q5#8U8%3Q0n9T9o4/0%0H12020R0U0w0c0e9!9$9(9*9%0e9t9f9y9A253;9D8P7g9^0n8N9`7$3m5;8T8_019X3p9T2v0w0U0x0n0x0L0%aa0H2J0n1,0n2@0w1+0$2i0f0n1U2J0E0V1!0c0n0U2E191}0b0P0uas0H1jaz0P0Z0d9#1-0P0`1-2#1BaP9:9v5O9=0X8F499_9L9{a%9}9J9 7r5t62a38 a69S9T0_0n9m1,ab0n190!0b341-2z0{0b1+b4aaacaBam0w8B0?0q0n0.bi2 1T0b2B0{25az24ac1,0?0bamav0b0u0x0?ao0q0.0%aX2|3Xa!a$0T6g5oa!9M4v9I2ia.7;bN5@9ubI4CbK9B4Ma(7P5d4Na,bTa)a00T6ua=940}a@a80n0F02030G0Y0e0u0%azalavaxbn8;1N0n2C0L0x0d0 0o0n0)2i0Ebe8;2D0Wasbjal1!2f0?2f1}1-bu0@3h1gcy2GaG1_1-aD0xaF0ubH8vbJ9E9?0g4%b(9G5t4(b,9Kb)5V6Ib=3Yb^a89#bw2f0n0oaKaA2E3#0*4k2C0Z2i2Fb42x0*cd1o2D2F0Q2r0baP999vbYcMb!cOa#b$0T6VbOdbbQdebScXcT3Ndf658Uc%9T9-9,9#9.dt9/d79;dbbL6,dgbU7Q5fcWdF5ddD5@b_9j90041k9v998U0w120y9i8*0N122q9V548{8}aY8*9l9nd+a49qcL3VaZdBdd5xcSdid`dIb.a/5I6|3Td8d?cN8JbL5Jd{a*3n3od~cY6*e99Oa^dTa40P5K030n0p0g2C0b3#bnbAak371`1-2Ganc}2haD0b1U0Hd22hd40UcKdzd/8Ad^9@6G3PdEd 7;5YdkdJ5/eUdMa8dO0g12ezdYa4dV04dXdSdO8{0z0zd%2b0E0b125ye=8U8W04c-0xe-8 e*040Xf6b?010w9R2#fb4Dd!04cd1JeNbZ8 d)e`9b0492f0e.120kfh5le|5wfr8`120W0Bfz4/f2f4fI6912fafv8 fe12fgfQfc0gfjfl1NfD01fqePfW12dR2`ekfRfxfMe{e}5Lf#9qfHeOfo9xeRcQ6Ga237bPeb5:eZeW7Qg4eie48ee69Fe8a;g1dhg34aeedm6Ga;e%9U8Uem12eo0i0uaw1!bpc92Ga`ezcp2 0w182f0Obq0n0Aexc`0Ub1aqcx1X2$0nc)210gaG0xgTal0lewbD0.d=gbdae7d_bNgge!eg4wgkd|bW3tdNf112fLfV4DfTf:1:fS04fUf,e)fY25f!f(9g12d*f{3YfBf?hc9p1297hk5{f*h20}e/fyg fAf=3rhod(fF9sf`d9eQg-eS3nb;g:g66sb+9~hL5/b;bXdAhGf~3nc!hKef8RcVhOhZ5Ic!gob_f-fcfK4khrdP0qh:h4h63vh,fi12fZfnhEfcf%hg5)91h?f/hv4/hihyi24/9qhC6yhcb#hH0ldfhYgl3n4}g@g3dog`h+itdOf20b8Zi7fN04h=iz2be/0ye;h78Uhie ibhA04ie4figf}5IdDild|dHh$im0ldLisiti%h`i304e,hz2be@f#f80bf@120Be_i-fsiCiMi.i@i5e:h:iKh:gr04eo1@gT2#1h2e2F250?a`2i16aj0w0DgMcHcJ0n370L0c0Lcaer0 eu0%0L1-0d0I2Kc`0?iLiQhgihhV6{eab/jLipjNe2h*i(iv124JiyiIa4f89di?04i_i}fsi=iDh3120Tj2hxj$f_jYf.04020v9(iHh_e)12i|h hdiOg*9wcaiS3m77jMe0k9ediYdikaeii(jTd,04g(2L0X0M0u1#9ej,hsdWh:j!ktj)fEj%i:h1kufdj.j:fCi`kBj?jHk2jJ7%eUiVeb7ig5h%k9e$i$kjg{jZe+0db8j$j(k2i*j+kAf$i@k+e5k$iBj=j0j}3Vi)5{fjb0j$hfkNk?hFgddd7ukb7;l8jPkc3Oa2jSk!h+j 04a|k*kDh5j0j/kFi9k_kFhtkxk%k)kKk:kClzi;lpkIhjk/8{i^lnk1k|dOe/lqj@f)km0NbEkokqksj=hnifjIk83Ogfk7g;7FkVim7H1(lglhe(kli,lH12k=g+f7kElQ3YlOlFiak,ick;lKltl!kOl$7Tl97Qmblclag_ejl;e?fFk5d@hU7%hJl)hP76hNa-ms7hhRkZkka4f23h0%h~l4i012iP5%iRmok9hXmrkW7=l,kgh)mzlhljl@m3iNl`k6k-j=m#ljlLl{mH04kMlMdUkwkFf8mYmGk3m)klk.j~m;04lPm~a4lslzlIm{k@m+m$m4m.mmgccP7%ikmPl-iokfkTir3wmLl6hH8bmc6`iXmvmQnskil=mBh|0.abf+n2l|i+k(1,lmlChqn5m5nMftm7l38e0C8y8f8t8h8q1l0c8kn#2W2RnJnY0C8i9u0-0/0;0%04.

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.