\section{Programmation dynamique}


Les questions suivantes sont toutes \`a r\'esoudre par la programmation dynamique. Voici une correction type pour que vous voyez quel genre de r\'eponse est attendue.

\subsection*{Exemple (0 points)}

Un mot $w$ sur l'alphabet \`a deux symboles $\{(,)\}$ est bien parenth\'es\'e si on peut associer chaque parenth\`ese ouvrante $x$ \`a une parenth\`ese fermante \`a droite de $x$ et que les associations soient \emph{sans collision} et \emph{ne se croisent pas}. Voir Figure~\ref{ref:croisment}.

\begin{figure}[h]
  \centerline{\includegraphics[width=8cm]{christoph2/croisement.pdf}}
  \caption{\`a gauche une association avec collision, au centre une avec croisement, et \`a droite une sans collision ni croisement.}
  \label{ref:croisment}
\end{figure}

Formellement on associe \`a un mot $w\in \{(,)\}^*$ un compteur $p[w]$ d\'efini comme le nombre de parenth\`eses ouvrantes dans $w$ moins le nombre de parenth\`eses fermantes dans $w$.  On dit que $w\in\{(,)\}^n$ est bien parenth\'es\'e si $p[w]=0$ et que pour tout $i=1,\ldots,n-1$, on ait $p[w_{1,\ldots,i}]\geq 0$, o\`u $w_{1,\ldots,i}$ est le mot constitu\'e des  $i$ premi\`eres lettres de $w$.

\begin{quote}
\begin{tabular}{ll}
bien parenth\'es\'e & mal parenth\'es\'e
\\ \hline
$\varepsilon$ &   (     \\
()             & )   \\
()()           & )( \\
(())            & (() \\
(())()          & ())(() \\
\end{tabular}
\end{quote}

Il est facile de d\'eterminer si un mot est bien parenth\'es\'e, en effectuant un unique parcours pendant lequel on maintien un compteur repr\'esentant $p[w_{1,\ldots,i}]$.  Mais si un mot n'est pas bien parenth\'es\'e, on peut toujours le rendre parenth\'es\'e en supprimant des parenth\`eses \`a diff\'erents endroits de la cha\^ine.  \'Etant donn\'ee un mot $w\in\{(,)\}^n$, d\'eterminer le nombre minimal de parenth\`eses \`a supprimer pour rendre $w$ bien parenth\'es\'e.  Une complexit\'e en $O(n^3)$ est attendue.

\paragraph{R\'eponse type~:}

Soit $A_{i,j}$ le nombre minimal de parenth\`eses \`a supprimer pour rendre le mot $w_{i,\ldots,j}$ bien parenth\'es\'e, avec $1\leq i\leq j\leq n$.  Nous \'etendons la notation \`a $i=j+1$ et d\'efinissons $A_{j+1,j}=0$, correspondant \`a la solution optimale pour le mot vide.

La r\'ecursion est sur la valeur $j-i$.  Le cas de base est $A_{j+1,j} = 0$ pour le mot vide.  Pour la r\'ecursion avec $j\geq i$, consid\'erons la premi\`ere lettre $w_{i}$ du mot $w_{i,\ldots,j}$ et consid\'erons une solution optimale.  Soit $w_i$ est supprim\'ee dans la solution optimale, et dans ce cas $A_{i,j} = 1 + A_{i+1,j}$ par composition des solutions. Soit cette lettre est associ\'ee \`a une lettre $w_\ell$ avec $i+1 \leq \ell \leq j$. Cette situation n'est possible seulement si $w_{i}=($ et $w_{\ell}=)$.  Les cha\^ines $w_{i+1,\ldots,\ell-1}$ et $w_{\ell+1,\ldots,j}$ forment des sous-probl\`emes ind\'ependants car les associations de parenth\`eses ne peuvent pas se croiser. Dans ce cas nous avons alors la r\'ecursion $A_{i,j} = A_{i+1,\ell-1} + A_{\ell+1,j}$.

En r\'esum\'e le programme dynamique consiste en $O(n^2)$ variables $A_{i,j}$, dont le cas de base est $A_{i,j}=0$ si $i=j+1$ et sinon
\[
A_{ij} = \min\left\{ 1 + A_{i+1,j}, \min_{\ell} A_{i+1,\ell-1} + A_{\ell+1,j} \right\},
\]
o\`u le minimum int\'erieur est pris sur les valeurs $i+1 \leq \ell \leq j$ avec $w_{i}=($ et $w_{\ell}=)$.  Par convention le minimum sur l'ensemble vide est d\'efini comme valant $+\infty$. La r\'eponse au probl\`eme est $A_{1,n}$.  Ces variables doivent \^etre calcul\'ees dans l'ordre suivant. D'abord pour tout $j=\{1,\ldots,n\}$ $A_{j+1,j}=0$ est pos\'e. Puis pour tout $k=0,\ldots,n-1$ (et dans cet ordre) et pour tout $j\in\{1+k,\ldots,n\}$, $A_{j-k,j}$ est calcul\'ee en utilisant la r\'ecursion ci-haute.

Comme il y a $O(n^2)$ variables et que chacune est calcul\'ee par minimisation sur $O(n)$ alternatives, le programme dynamique a une complexit\'e en temps de $O(n^3)$.  Il existe de meilleurs algorithmes pour ce probl\`eme, mais ce n'est pas le propos pour l'instant.

\subsection{Coefficients binomiaux (1 points)}

Le d\'eveloppement de l'expression $(a+b)^n$ est une somme d'expressions de la forme $\binom{n}{k} a^k b^{n-k}$ pour tout $k=0,\ldots,n$.  Par exemple $(a+b)^3 = a^3 + 3a^2b + 3 ab^2 + b^3$. Donnez un programme dynamique pour calculer $\binom{n}{k}$ en temps $O(n^2)$.

\subsection{Subsetsum  (2 points)}

Dimitri fabrique un mod\`ele d'avion. Il estime que pour que le centre de gravit\'e soit \`a l'endroit n\'ecessaire, il doit ajouter du leste dans le nez de l'avion.  Plus pr\'ecis\'ement il doit ajouter exactement $L$ grammes dans le nez.  Pour cela il dispose de $n$ billes de diff\'erents poids, la $i$-\`eme bille pesant exactement $p_i$ grammes. \'Etant donn\'ees $L$ et $p_1,\ldots,p_n$, Dimitri doit d\'ecider s'il existe un ensemble $S \subseteq \{1,\ldots,n\}$ avec $\sum_{i\in S} p_i = L$.  Aidez Dimitri avec un programme dynamique de complexit\'e $O(L n)$.

\subsection{Emballage de jouets (4 points)}

Odile doit s'occuper d'une machine \'etrange \`a fabriquer des jouets. Elle fabrique deux sortes de jouets, des voitures pesant 100 grammes et des camions pesant 150 grammes. Ce qui est \'etrange est dans une journ\'ee la machine fabrique $n$ jouets selon un programme pr\'ed\'efini et d\'ecrit par un vecteur $x\in\{100,150\}^n$, o\`u $x_i=150$ ssi le $i$-\`eme jouet produit dans la journ\'ee est un camion.  Odile doit emballer les jouets dans des cartons au fur et \`a mesure qu'ils sont produits, en respectant l'ordre de production. Pour cela elle dispose d'un stock in\'epuisable de $k$ diff\'erents cartons.  Le $j$-\`eme type de carton lui co\^ute $p_j$ Euros \`a l'unit\'e et peut contenir plusieurs jouets d'un poids total ne d\'epassant pas $c_j$ grammes.


\begin{figure}[h]
  \centerline{\includegraphics[width=15cm]{christoph2/emballer.pdf}}
  \caption{Un exemple au probl\`eme d'emballage de jouets. Odile pourrait avoir envie d'emballer les trois premi\`eres voitures dans un carton \`a 13 Euros, qui minimise le ratio $p_{j}/c_{j}$. Mais cette approche gloutonne finalement m\`ene \`a une solution sur-optimale.}
  \label{ref:emballer}
\end{figure}


\'Etant donn\'ees les entiers $n,k$ avec $1\leq k\leq n$ et les vecteurs $x\in\{100,150\}^n$ et $p,c \in \mathbb N^k$ avec $c_1\geq 150$, aidez Odile \`a d\'eterminer le co\^ut total minimal des cartons n\'ecessaires pour emballer tous les jouets produits pendant la journ\'ee.

Il existe une solution de complexit\'e en temps $O(n^2)$.  N\'eanmoins des points partiels sont donn\'ees pour des algorithmes de plus grande complexit\'e.

\begin{quote}
\begin{tabular}{ll}
complexit\'e & points obtenus
\\ \hline
  $O(n^3)$ & 2 points \\
  $O(n^2 k)$ & 3 points \\
  $O(n^2 \log k)$ & 3 points \\
  $O(n^2)$ & 4 points
\end{tabular}
\end{quote}

