{"id":289,"date":"2016-02-01T13:23:26","date_gmt":"2016-02-01T12:23:26","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=289"},"modified":"2022-12-03T22:57:02","modified_gmt":"2022-12-03T21:57:02","slug":"programmation-dynamique","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/algoritmico\/programacion-dinamica-2\/","title":{"rendered":"Programaci\u00f3n din\u00e1mica"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"289\" class=\"elementor elementor-289\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-79b1511 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"79b1511\" 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-0acf913\" data-id=\"0acf913\" 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-a78b8ba elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a78b8ba\" 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\/algorithmique\/\">\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\">Algorithmique<\/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-5d498ed\" data-id=\"5d498ed\" 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-d16e4c6 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"d16e4c6\" 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-0272ba7\" data-id=\"0272ba7\" 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-4deeb42 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"4deeb42\" 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\/Programmation_dynamique\" 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-fe95a82 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fe95a82\" 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-68d1f05b\" data-id=\"68d1f05b\" 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-597deca1 elementor-widget elementor-widget-text-editor\" data-id=\"597deca1\" 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=\"Alternar tabla de contenidos\"><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 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/programacion-dinamica-2\/#Programmation-dynamique\" >Programmation dynamique<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/programacion-dinamica-2\/#Principe\" >Principe<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/programacion-dinamica-2\/#Exemple-produit-de-matrices\" >Exemple : produit de matrices<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/programacion-dinamica-2\/#Exemple-le-change-de-monnaie\" >Exemple: le change de monnaie<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Programmation-dynamique\"><\/span>Programmation dynamique<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><em>La programmation dynamique est utilis\u00e9 pour la r\u00e9solution de nombreux probl\u00e8mes provenant de la recherche op\u00e9rationnelle, c&rsquo;est pourquoi nous ne listerons pas les tutoriels li\u00e9s \u00e0 cette m\u00e9thode.<\/em><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p>La Programmation Dynamique est une m\u00e9thode exacte de r\u00e9solution de probl\u00e8mes<br \/>d\u2019optimisation, due essentiellement \u00e0 R. <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-bellman\/\">Bellman<\/a> (1957).<\/p>\n<p><\/p>\n<p><\/p>\n<p>Plus pr\u00e9cis\u00e9ment, la programmation dynamique est un paradigme de conception d\u2019algorithmes qu\u2019on peut appliquer pour r\u00e9soudre un probl\u00e8me s&rsquo;il r\u00e9pond \u00e0 l&rsquo;optimalit\u00e9 de Bellman.<\/p>\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;\"><strong>D\u00e9finition. <\/strong><em>Optimalit\u00e9 de <\/em><em>Bellman.<\/em> Un probl\u00e8me poss\u00e8de la propri\u00e9t\u00e9 de sous-structure optimale si une solution optimale contient la solution optimale des sous-probl\u00e8mes.<\/div>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-903 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/progdyn.png\" alt=\"diviser pour r\u00e9gner programmation dynamique\" width=\"757\" height=\"246\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/progdyn.png 757w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/progdyn-300x97.png 300w\" sizes=\"(max-width: 757px) 100vw, 757px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p>La programmation dynamique ressemble dans l&rsquo;id\u00e9e \u00e0 la m\u00e9thode <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/divide-y-venceras\/\">diviser et r\u00e9gner<\/a>. La diff\u00e9rence significative entre ces deux m\u00e9thodes est que la programmation dynamique permet aux sous-probl\u00e8mes de se superposer. Autrement dit, un sous-probl\u00e8me peut \u00eatre utilis\u00e9 dans la solution de deux sous-probl\u00e8mes diff\u00e9rents. Tandis que l\u2019approche diviser et r\u00e9gner cr\u00e9e des sous-probl\u00e8mes s\u00e9par\u00e9s pouvant \u00eatre r\u00e9solus ind\u00e9pendamment l\u2019un de l\u2019autre.<\/p>\n<p><\/p>\n<p><\/p>\n<p>La diff\u00e9rence fondamentale entre ces deux m\u00e9thodes est donc : les sous-probl\u00e8mes dans la programmation dynamique peuvent \u00eatre en interaction, alors dans la m\u00e9thode diviser et r\u00e9gner, ils ne le sont pas.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Une seconde diff\u00e9rence entre ces deux m\u00e9thodes est, comme illustr\u00e9 par la figure ci-dessus, est que la m\u00e9thode diviser et r\u00e9gner est r\u00e9cursive, la r\u00e9cursion prend le probl\u00e8me global pour le d\u00e9couper en probl\u00e8me \u00e9l\u00e9mentaire. La programmation dynamique est une m\u00e9thode dont les calculs se font de bas en haut : on commence par r\u00e9soudre les plus petits sous-probl\u00e8mes. En combinant leur solution, on obtient les solutions des sous-probl\u00e8mes de plus en plus grands.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Principe\"><\/span>Principe<span class=\"ez-toc-section-end\"><\/span><\/h2>\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;\">\n<p>Le paradigme se d\u00e9compose en quatre probl\u00e9matiques :<\/p>\n<ol style=\"text-align: justify;\">\n<li>Caract\u00e9risation de la structure d\u2019une solution optimale.<\/li>\n<li>D\u00e9finition r\u00e9cursive de la valeur de la solution optimale.<\/li>\n<li>Calcul ascendant de la solution.<\/li>\n<li>Construction de la solution \u00e0 partir du calcul ascendant.<\/li>\n<\/ol>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>On construit une table pour m\u00e9moriser les calculs d\u00e9j\u00e0 effectu\u00e9s : \u00e0 chaque \u00e9l\u00e9ment correspondra la solution d\u2019un et d\u2019un seul probl\u00e8me interm\u00e9diaire, et un pour la solution finale. Il faut donc qu\u2019on puisse d\u00e9terminer les sous-probl\u00e8mes qui seront trait\u00e9s au cours du calcul.<\/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;\">\n<p>Il existe deux approches pour remplir le tableau :<\/p>\n<ul style=\"text-align: justify;\">\n<li>It\u00e9rative : On initialise les \u00ab\u00a0cases\u00a0\u00bb correspondant aux cas de base.<br \/>On remplit ensuite la table selon un ordre bien pr\u00e9cis \u00e0 d\u00e9terminer : on commence par les probl\u00e8mes de \u00ab\u00a0taille\u00a0\u00bb la plus petite possible, on termine par la solution du probl\u00e8me principal : il faut qu\u2019\u00e0 chaque calcul, on n\u2019utilise que les solutions d\u00e9j\u00e0 calcul\u00e9es.<\/li>\n<li>R\u00e9cursive : M\u00eame principe que l&rsquo;approche it\u00e9rative, cette m\u00e9thode quant \u00e0 elle ne calculera que le strict n\u00e9cessaire pour atteindre l&rsquo;objectif donn\u00e9.<\/li>\n<\/ul>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-produit-de-matrices\"><\/span>Exemple : produit de matrices<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Soient <strong>n<\/strong> matrices M<sub>1<\/sub>, &#8230;, M<sub>n<\/sub>, chaque matrice \u00e0 un certain nombre m<sub>i<\/sub> de lignes et m<sub>i+1<\/sub> colonnes, les entr\u00e9es sont des nombres r\u00e9els (<a href=\"https:\/\/complex-systems-ai.com\/es\/ayuda-con-la-decision\/modelado-lineal\/\">probl\u00e8me lin\u00e9aire<\/a>). Nous cherchons \u00e0 calculer M<sub>1<\/sub>*&#8230;*M<sub>n<\/sub> de fa\u00e7on \u00e0 minimiser le nombre d&rsquo;op\u00e9rations.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Notons c<sub>ij<\/sub> le nombre d&rsquo;op\u00e9rations pour calculer M<sub>i<\/sub>*&#8230;*M<sub>j<\/sub>. On a alors c<sub>ii<\/sub>=0 et c<sub>i(i+1)<\/sub>=m<sub>(i-1)<\/sub>*m<sub>i<\/sub>*m<sub>(i+1)<\/sub> op\u00e9rations. D\u00e9coupons ce sous-probl\u00e8me en calculant le meilleur c<sub>ij<\/sub> avec M<sub>i<\/sub>*&#8230;*M<sub>k<\/sub> et M<sub>(k+1)<\/sub>*&#8230;*M<sub>j<\/sub>. Alors : c<sub>ij<\/sub> = min [c<sub>ik<\/sub> + c<sub>(k+1)j<\/sub> + m<sub>i<\/sub>*m<sub>(k+1)<\/sub>*m<sub>(j+1)<\/sub>] avec <strong>k<\/strong> de <strong>i<\/strong> \u00e0 <strong>j-1<\/strong>, le dernier terme revient \u00e0 multiplier les r\u00e9sultats du produit de matrices de <strong>i<\/strong> \u00e0 <strong>k<\/strong> avec celui de <strong>k+1<\/strong> \u00e0<strong> j<\/strong>.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<p>Nous avons donc le programme suivant :<\/p>\n<ul>\n<li style=\"text-align: justify;\">c<sub>ij<\/sub> = 0 si i = j;<\/li>\n<li style=\"text-align: justify;\">c<sub>i(i+1)<\/sub>=m<sub>(i-1)<\/sub>*m<sub>i<\/sub>*m<sub>(i+1)<\/sub>;<\/li>\n<li style=\"text-align: justify;\">c<sub>ij<\/sub> = min [c<sub>ik<\/sub> + c<sub>(k+1)j<\/sub> + m<sub>i<\/sub>*m<sub>(k+1)<\/sub>*m<sub>(j+1)<\/sub>] sinon.<\/li>\n<\/ul>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Le tableau du programme dynamique prend en entr\u00e9e le nombre d&rsquo;op\u00e9rations effectu\u00e9es en fonction des matrices choisies. Prenons l&rsquo;exemple suivant :<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">i<\/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<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\">7<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">m<sub>i<\/sub><\/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\">35<\/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\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/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\">25<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Le tableau initial est le suivant :<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">c<sub>ij<\/sub><\/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<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\">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\">&#8211;<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Puis nous pouvons calculer c<sub>ij<\/sub> avec deux matrices (sans principe de sous-structure) :<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">c<sub>ij<\/sub><\/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<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\">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\">15750<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">2625<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">750<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">1000<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">5000<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">\u00a0<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Le reste du tableau se remplit diagonale par diagonale suivant la r\u00e8gle d\u00e9crite plus haut :<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">c<sub>ij<\/sub><\/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<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\">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\">15750<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">7875<\/td>\n<td align=\"center\" valign=\"top\">9375<\/td>\n<td align=\"center\" valign=\"top\">11875<\/td>\n<td align=\"center\" valign=\"top\">15125<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">2625<\/td>\n<td align=\"center\" valign=\"top\">4375<\/td>\n<td align=\"center\" valign=\"top\">7125<\/td>\n<td align=\"center\" valign=\"top\">10500<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">750<\/td>\n<td align=\"center\" valign=\"top\">2500<\/td>\n<td align=\"center\" valign=\"top\">5375<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">1000<\/td>\n<td align=\"center\" valign=\"top\">3500<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<td align=\"center\" valign=\"top\">5000<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Le r\u00e9sultat est obtenu pour i=1 et j=6, soit la case en haut \u00e0 droite du tableau. Le co\u00fbt minimal est donc de 15125 op\u00e9rations. Une nouvelle question se pose alors : comment a-t-on proc\u00e9d\u00e9 pour avoir un nombre de calcul minimal ?<\/p>\n<p><\/p>\n<p><\/p>\n<p>Lorsque nous calculons le co\u00fbt minimal pour chaque case, nous effectuons un choix parmi deux configurations. Par exemple pour calculer c<sub>13<\/sub>, nous prenons le minimum entre c<sub>12<\/sub>*M<sub>3<\/sub> et M<sub>1<\/sub>*c<sub>23<\/sub>. Il suffit de noter le choix effectu\u00e9 afin de connaitre l&rsquo;ordre de calcul du produit matriciel.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">K<sub>ij<\/sub><\/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<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\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">&#8211;<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">&#8211;<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\"><span style=\"color: #0000ff;\">1<\/span><\/td>\n<td align=\"center\" valign=\"top\">3<\/td>\n<td align=\"center\" valign=\"top\">3<\/td>\n<td align=\"center\" valign=\"top\"><span style=\"color: #ff0000;\">3<\/span><\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">3<\/td>\n<td align=\"center\" valign=\"top\">3<\/td>\n<td align=\"center\" valign=\"top\">3<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\"><span style=\"color: #0000ff;\">&#8211;<\/span><\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">3<\/td>\n<td align=\"center\" valign=\"top\">3<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\"><span style=\"color: #0000ff;\">5<\/span><\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\"><span style=\"color: #ff0000;\">&#8211;<\/span><\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\"><span style=\"color: #0000ff;\">&#8211;<\/span><\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<td align=\"center\" valign=\"top\">&#8211;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Le tableau se lit ainsi : pour calculer M<sub>i<\/sub>*M<sub>j<\/sub>, on pose k = K<sub>ij<\/sub> donn\u00e9 par le tableau puis on calcule M<sub>i<\/sub>*&#8230;*M<sub>k<\/sub> et M<sub>(k+1)<\/sub>*&#8230;*M<sub>j<\/sub> que l&rsquo;on multiplie ensuite entre elles.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Dans notre exemple, pour calculer <span style=\"color: #ff0000;\">c<sub>16<\/sub><\/span>, nous calculons c<sub>13<\/sub>*c<sub>46<\/sub>; pour calculer <span style=\"color: #0000ff;\">c<sub>13<\/sub><\/span>, nous calculons M<sub>1<\/sub>*c<sub>23<\/sub>; pour calculer <span style=\"color: #0000ff;\">c<sub>46<\/sub>\u00a0 <\/span>nous calculons c<sub>45<\/sub>*M<sub>6<\/sub>.<\/p>\n<p><\/p>\n<p><\/p>\n<p>La plupart des <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algorithme<\/a> bas\u00e9s sur la programmation dynamique retienne en m\u00e9moire le choix effectu\u00e9 pour chaque calcul. Bien souvent le r\u00e9sultat n&rsquo;est pas important, le parcours pour l&rsquo;atteindre l&rsquo;est.<\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-le-change-de-monnaie\"><\/span>Exemple: le change de monnaie<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Nous souhaitons faire le change sur 67\u00a3. Pour cela nous voulons utiliser le minimum de pi\u00e8ces de type: 1, 5, 10, 25.<\/p>\n<p><\/p>\n<p><\/p>\n<p>Ici il est facile de deviner la solution optimale 67=2*25+10+5+2*1. En choisissant toujours la pi\u00e8ce de plus grande valeur possible, nous obtenons une solution (par <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/algoritmo-naif-codicia-enumeracion\/\">algorithme glouton<\/a>).<\/p>\n<p><\/p>\n<p><\/p>\n<p>Le probl\u00e8me s&rsquo;\u00e9crit de mani\u00e8re suivant: Soit D={ d<sub>1<\/sub>,..,d<sub>k<\/sub>} un nombre fini de valeur de pi\u00e8ce. On suppose que chaque d<sub>i <\/sub>est un entier et que l&rsquo;ensemble soit tri\u00e9 par valeur croissante. Chaque valeur de pi\u00e8ce est disponible en illimit\u00e9. Le probl\u00e8me est de faire le change sur une valeur de n\u00a3 avec un nombre minimal de pi\u00e8ce, si d<sub>k<\/sub> =1 alors il existe toujours une solution.<\/p>\n<p><\/p>\n<p><\/p>\n<p>La m\u00e9thode gloutonne ne donne pas toujours de solution optimale. Par exemple, D={25,10,1} et n=30. La m\u00e9thode optimale donnera la solution suivante: 25+5*1, qui est moins bonne que 3*10.<\/p>\n<p><\/p>\n<p><\/p>\n<p><em>Etape 1: Caract\u00e9riser\u00a0la sous-structure optimale.<\/em> D\u00e9finissons C[j] comme la solution optimale pour la somme j\u00a3. Nous pouvons ainsi enlever une pi\u00e8ce et ainsi trouver une solution optimale pour C[j]=1+C[j-di].<\/p>\n<p><\/p>\n<p><\/p>\n<p><em>Etape 2: Valeur de la solution optimale.<\/em>\u00a0Nous pouvons d\u00e9finir r\u00e9cursivement la solution optimale \u00e0 partir de la sous-structure.<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6434 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/dynprog.png\" alt=\"change de monnaie programmation dynamique\" width=\"386\" height=\"86\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/dynprog.png 386w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/dynprog-300x67.png 300w\" sizes=\"(max-width: 386px) 100vw, 386px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p><em>Etape 3: Algorithme. <\/em><\/p>\n<p><\/p>\n<p><\/p>\n<div>\n<pre>Coin-Changing(n,d,k)\nC[0]=0;\nFor j from 1 to n\n     C[j]=inf;\n     For i from 1 to k\n          If j&gt;=di and C[j-di]&lt;C[j]\u00a0then\n               C[j]=1+C[j-di]\n               Denom[j]=di\nReturn C\n<\/pre>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>On utilise un tableau suppl\u00e9mentaire appeler Denom, tel que Denom[j] repr\u00e9sente la pi\u00e8ce utiliser pour obtenir une solution optimale pour une somme j\u00a3. Si on remonte Denom de la valeur de la pi\u00e8ce jusqu&rsquo;\u00e0 atteindre j=1, alors nous connaissons la selection de pi\u00e8ce qui a \u00e9t\u00e9 faite. Prenons l&rsquo;exemple avec les pi\u00e8ces suivantes: 1, 5, 10, 25:<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>j<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>4<\/td>\n<td>5<\/td>\n<td>6<\/td>\n<td>7<\/td>\n<td>8<\/td>\n<td>9<\/td>\n<td>10<\/td>\n<td>11<\/td>\n<td>12<\/td>\n<td>13<\/td>\n<td>14<\/td>\n<td>15<\/td>\n<\/tr>\n<tr>\n<td>C[j]<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>4<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>4<\/td>\n<td>5<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>4<\/td>\n<td>5<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>Denom[j]<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>5<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>10<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>5<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><\/p>\n<p><\/p>\n<p>A partir d&rsquo;une somme n\u00a3, nous pouvons trouver toutes les combinaisons de pi\u00e8ce permettant de faire le change. Prenons les m\u00eames valeurs de pi\u00e8ce : 1, 5, 10, 25. Par exemple, pour N=4, D={1,2,3} il y a quatre solutions : {1,1,1,1}, {1,1,2}, {2,2} et {1,3}.<\/p>\n<p><\/p>\n<p><\/p>\n<p><em>Etape 1:<\/em> Sous-structure optimale,\u00a0 C(N,m) peut \u00eatre partitionner un deux ensembles:<\/p>\n<p><\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>Les solutions ne contenant aucune pi\u00e8ce d<sub>m<\/sub><\/li>\n<li>les solutions contenant au moins une pi\u00e8ce d<sub>m<\/sub><\/li>\n<\/ol>\n<p><\/p>\n<p><\/p>\n<p>Si une solution ne contient pas de pi\u00e8ce d<sub>m<\/sub>, alors nous pouvons r\u00e9soudre le sous-probl\u00e8me de N avec D={d<sub>1<\/sub>, ..,d<sub>m-1<\/sub>}, soit les solutions de C(N,m-1).<\/p>\n<p><\/p>\n<p><\/p>\n<p>Si une solution contient d<sub>m<\/sub>, alors nous allons enlever une pi\u00e8ce d<sub>m<\/sub>, il faut donc r\u00e9soudre le sous-probl\u00e8me N- d<sub>m<\/sub> , avec D={d<sub>1<\/sub>, ..,d<sub>m<\/sub>}. Soit r\u00e9soudre le probl\u00e8me suivant C(N- d<sub>m<\/sub>, m).<\/p>\n<p><\/p>\n<p><\/p>\n<p><em>Etape 2:<\/em> La r\u00e8gle est la suivante: C(N-m)=+ C(N- d<sub>m<\/sub>, m) avec les conditions de base:<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>C(N,m)=1, N=0<\/li>\n<li>C(N,m)=0, N&lt;0<\/li>\n<li>C(N,m)=0, N&gt;=1, m&lt;=0<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<p><em>Etape 3:<\/em> Les solutions de l&rsquo;algorithmes sont report\u00e9 dans un tableau de la forme<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>n\/d<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>4<\/td>\n<td>5<\/td>\n<td>6<\/td>\n<td>7<\/td>\n<td>8<\/td>\n<td>9<\/td>\n<td>10<\/td>\n<td>11<\/td>\n<td>12<\/td>\n<td>13<\/td>\n<td>14<\/td>\n<td>15<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<td>4<\/td>\n<\/tr>\n<tr>\n<td>10<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>4<\/td>\n<td>4<\/td>\n<td>4<\/td>\n<td>4<\/td>\n<td>4<\/td>\n<td>6<\/td>\n<\/tr>\n<tr>\n<td>25<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>4<\/td>\n<td>4<\/td>\n<td>4<\/td>\n<td>4<\/td>\n<td>4<\/td>\n<td>6<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\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>Algoritmos P\u00e1gina de inicio Wiki Programaci\u00f3n din\u00e1mica La programaci\u00f3n din\u00e1mica se utiliza para resolver muchos problemas de la investigaci\u00f3n de operaciones, es por eso que \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":1062,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-289","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/289","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=289"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/289\/revisions"}],"predecessor-version":[{"id":17940,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/289\/revisions\/17940"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=289"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}