{"id":2334,"date":"2016-05-17T10:50:42","date_gmt":"2016-05-17T09:50:42","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=2334"},"modified":"2022-12-03T22:58:58","modified_gmt":"2022-12-03T21:58:58","slug":"probleme-du-sac-a-dos","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/backpack-problem\/","title":{"rendered":"Backpack problem"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"2334\" class=\"elementor elementor-2334\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-549fc08 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"549fc08\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-3d800e3\" data-id=\"3d800e3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d717408 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"d717408\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/problemes-industriels-et-reduction-polynomiale\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">R\u00e9duction polynomial<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-09b31b2\" data-id=\"09b31b2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5f4c509 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5f4c509\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-9df5651\" data-id=\"9df5651\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-498a882 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"498a882\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Probl%C3%A8me_du_sac_%C3%A0_dos\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1d059073 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1d059073\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-477ee55f\" data-id=\"477ee55f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4fb15a5c elementor-widget elementor-widget-text-editor\" data-id=\"4fb15a5c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/backpack-problem\/#Probleme-du-sac-a-dos\" >Probl\u00e8me du sac \u00e0 dos<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/backpack-problem\/#Enonce\" >\u00c9nonc\u00e9<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/backpack-problem\/#Methodes-de-resolution\" >M\u00e9thodes de r\u00e9solution<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/backpack-problem\/#Algorithme-glouton\" >Algorithme glouton<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/backpack-problem\/#Programmation-dynamique\" >Programmation dynamique<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"h2_like\"><span class=\"ez-toc-section\" id=\"Probleme-du-sac-a-dos\"><\/span>Probl\u00e8me du sac \u00e0 dos<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p class=\"h2_like\">Le probl\u00e8me du sac \u00e0 dos est l&rsquo;un des 21 probl\u00e8mes NP-complets de Richard Karp, expos\u00e9s dans son article de 1972.<\/p>\n<p><\/p>\n<p><\/p>\n<h1 id=\"art_title\" class=\"h2_like wp-block-heading\"><span class=\"ez-toc-section\" id=\"Enonce\"><\/span>\u00c9nonc\u00e9<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Le probl\u00e8me du sac \u00e0 dos mod\u00e9lise une situation analogue au remplissage d&rsquo;un sac \u00e0 dos, ne pouvant supporter plus d&rsquo;un certain poids, avec tout ou partie d&rsquo;un ensemble donn\u00e9 d&rsquo;objets ayant chacun un poids et une valeur. Les objets mis dans le sac \u00e0 dos doivent maximiser la valeur totale, sans d\u00e9passer le poids maximum.<\/div>\n<p><\/p>\n<p><\/p>\n<p>La forme la plus commune est le probl\u00e8me de sac \u00e0 dos 0-1 (0-1 KP), restreignant le nombre de copies x<sub>i<\/sub> de chaque objet i \u00e0 un exemplaire au maximum. Soient un ensemble de n objet, muni d&rsquo;un poids w<sub>i<\/sub> et d&rsquo;une utilit\u00e9 v<sub>i<\/sub>, et la capacit\u00e9 du sac \u00e0 dos W, le probl\u00e8me s&rsquo;\u00e9crit comme suit:<\/p>\n<p><\/p>\n<p><\/p>\n<dl>\n<dd>maximize \u2211<sub>i=1<\/sub><sup>n<\/sup> v<sub>i<\/sub>*x<sub>i<\/sub><\/dd>\n<dd>subject to\u00a0\u2211<sub>i=1<\/sub><sup>n<\/sup> v<sub>i<\/sub>*x<sub>i<\/sub> \u2264 W and x<sub>i<\/sub> \u2208 {0,1}.<\/dd>\n<\/dl>\n<p><\/p>\n<p><\/p>\n<p>Le probl\u00e8me du sac \u00e0 dos limit\u00e9 (bounded knapsack problem BKP) retire la restriction de limitation de l&rsquo;objet par une limitation born\u00e9e par un entier c<sub>i<\/sub>:<\/p>\n<p><\/p>\n<p><\/p>\n<dl>\n<dd>maximize \u2211<sub>i=1<\/sub><sup>n<\/sup> v<sub>i<\/sub>*x<sub>i<\/sub><\/dd>\n<dd>subject to\u00a0\u2211<sub>i=1<\/sub><sup>n<\/sup> v<sub>i<\/sub>*x<sub>i<\/sub> \u2264 W and x<sub>i<\/sub> \u2208 {0, &#8230; , c<sub>i<\/sub>}.<\/dd>\n<\/dl>\n<p><\/p>\n<p><\/p>\n<p>Le probl\u00e8me du sac \u00e0 dos illimit\u00e9 (unbounded knapsack problem UKP) ne place aucune restriction sur le nombres de copies de chaque objet.<\/p>\n<p><\/p>\n<p><\/p>\n<dl>\n<dd>maximize \u2211<sub>i=1<\/sub><sup>n<\/sup> v<sub>i<\/sub>*x<sub>i<\/sub><\/dd>\n<dd>subject to\u00a0\u2211<sub>i=1<\/sub><sup>n<\/sup> v<sub>i<\/sub>*x<sub>i<\/sub> \u2264 W and 0\u2264x<sub>i<\/sub> .<\/dd>\n<\/dl>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-10228 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/0-1-knapsack-problem.jpg\" alt=\"probl\u00e8me du sac \u00e0 dos 0-1 knapsack NP r\u00e9duction\" width=\"402\" height=\"285\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/0-1-knapsack-problem.jpg 402w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/0-1-knapsack-problem-300x213.jpg 300w\" sizes=\"(max-width: 402px) 100vw, 402px\" \/><\/p>\n<p>Il existe bien d&rsquo;autres variantes du probl\u00e8me du sac \u00e0 dos qui sont d\u00e9crite dans une autre page. Merci de vous r\u00e9f\u00e9rer \u00e0 la <a href=\"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/\">R\u00e9duction polynomiale<\/a>.<\/p>\n<p><\/p>\n<p><\/p>\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Methodes-de-resolution\"><\/span>M\u00e9thodes de r\u00e9solution<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Algorithme-glouton\"><\/span>Algorithme glouton<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>L&rsquo;id\u00e9e est d&rsquo;ajouter en priorit\u00e9 les objets les plus efficaces, jusqu&rsquo;\u00e0 saturation du sac\u00a0:<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre> Trier les objets par ordre d\u00e9croissant d'efficacit\u00e9\nw_conso := 0\n\n<b>pour<\/b> i <b>de<\/b> 1 <b>\u00e0<\/b> n\n  <b>si<\/b> w[i] + w_conso \u2264 W <b>alors<\/b>\n    x[i] := 1\n    w_conso := w_conso + w[i]\n  <b>sinon<\/b>\n    x[i] := 0\n  <b>fin si<\/b>\n<b>fin pour <\/b>\n<\/pre>\n<\/div>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Programmation-dynamique\"><\/span>Programmation dynamique<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Le probl\u00e8me du sac \u00e0 dos poss\u00e8de la propri\u00e9t\u00e9 de sous-structure optimale, i.e. que l\u2019on peut construire la solution optimale du probl\u00e8me \u00e0 k variables \u00e0 partir du probl\u00e8me \u00e0 k &#8211; 1 variables.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Soit F<sub>k<\/sub>(E) le meilleur cout pour remplir un sac de taille E avec les k<br \/>premiers objets. La r\u00e9currence montre queF<sub>k<\/sub>(E) = max{F<sub>k\u22121<\/sub>(E), F<sub>k\u22121<\/sub>(E \u2212 w<sub>k<\/sub>)+v<sub>k<\/sub>},<\/div>\n<p><\/p>\n<p><\/p>\n<p>en effet l\u2019ajout d\u2019un nouvel objet augmente ou non le meilleur cout. Dans le cas o\u00f9 le nouvel objet n\u2019est pas rajout\u00e9 au sac, F<sub>k<\/sub>(E) est \u00e9gale \u00e0 F<sub>k\u22121<\/sub>(E). Dans le cas o\u00f9 le nouvel objet offre une meilleure utilit\u00e9, i.e. dans le cas o\u00f9 l\u2019objet n\u2019est pas pr\u00e9sent mais que le sac (sans l\u2019objet) poss\u00e8de la place suffisante pour accueillir le nouvel \u00e9l\u00e9ment, et qu\u2019il soit optimal (soit la formule F<sub>k\u22121<\/sub>(E \u2212 w<sub>k<\/sub>)), alors F<sub>k<\/sub>(E) est \u00e9gale \u00e0 F<sub>k\u22121<\/sub>(E \u2212 w<sub>k<\/sub>) + v<sub>k<\/sub>, v<sub>k<\/sub> \u00e9tant l\u2019utilit\u00e9 du nouvel objet rajout\u00e9 dans le sac d\u00e9crit pr\u00e9c\u00e9demment.<\/p>\n<p>Nous donc cherchons \u00e0 calculer F<sub>n<\/sub>(W), avec n le nombre total d\u2019objet et W la taille maximale du sac \u00e0 dos \u00e9tudi\u00e9.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre><b>pour<\/b> c <b>de<\/b> 0 <b>\u00e0<\/b> W <b>faire<\/b>\n  T[0,c] := 0\n<b>fin pour<\/b>\n\n<b>pour<\/b> i <b>de<\/b> 1 <b>\u00e0<\/b> n <b>faire<\/b>\n  <b>pour<\/b> c <b>de<\/b> 0 <b>\u00e0<\/b> W <b>faire<\/b>\n    <b>si<\/b> c&gt;=w[i] <b>alors<\/b>\n      T[i,c] := max(T[i-1,c], T[i-1, c-w[i]] + p[i])\n    <b>sinon<\/b>\n      T[i,c] := T[i-1,c]\n    <b>fin si<\/b>\n  <b>fin pour<\/b>\n<b>fin pour <\/b><\/pre>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Nous disposons des \u00e9l\u00e9ments suivants : C = 8, et cinq objets d\u00e9crits dans<br \/>le tableau ci-dessous<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"example\" style=\"text-align: justify;\">\n<div class=\"example_item\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>i <\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>1<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>2<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>3<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>4<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>5<\/strong><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>p_i<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>u_i<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">18<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">20<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Nous obtenons le tableau de r\u00e9sultat du sac \u00e0 dos suivant :<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"example\" style=\"text-align: justify;\">\n<div class=\"example_item\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>E|i<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>1<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>2<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>3<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>4<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>5<\/strong><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>0<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>1<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>2<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>3<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>4<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">18<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">6<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>5<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">21<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">20<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">20<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">6<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>6<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">24<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">24<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">20<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">18<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>7<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">33<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">26<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">26<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">18<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>8<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">35<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">30<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">26<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">18<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>La solution optimale de 25 est obtenue avec les \u00e9l\u00e9ments 1 et 3 d\u2019apr\u00e8s le second<br \/><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithme<\/a> du sac \u00e0 dos :<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"example\" style=\"text-align: justify;\">\n<div class=\"example_item\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>k<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>E<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\"><strong>x[k]<\/strong><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>conso = conso_1 + conso_3 = 8.<\/p>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Polynomial reduction Wiki homepage Knapsack problem The knapsack problem is one of Richard Karp&#039;s 21 NP-complete problems, \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":3526,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2334","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2334","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=2334"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2334\/revisions"}],"predecessor-version":[{"id":17954,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2334\/revisions\/17954"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3526"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=2334"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}