\begin{questions}
\item Rappelons avant tout la fonction récursive initiale du problème :

\begin{listing}{}{04-sac-a-dos-recur.py}\end{listing}

\begin{itemize}
\item \textit{Approche dynamique de type \og Top Down \fg}.

\Par

Pour améliorer cette fonction récursive, il nous faut mémoriser les\linebreak solutions aux sous-problèmes (mémoïsation). Nous allons donc\linebreak stocker les valeurs de \texttt{V[i][p]}, avec $0 \leqslant i \leqslant n$ et $0 \leqslant p \leqslant P$, où $P$ est le poids maximal autorisé, dans une liste nommée par exemple \texttt{temp}.

La solution est très proche de l'initiale.

\newpage


\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/04-sac-a-dosTD.py}}}
\vspace*{-10pt}
\begin{listing}{}{04-sac-a-dosTD.py}\end{listing}

\Par\Par

Ce qui donne pour notre exemple:

\hrulefill
{\ttfamily

\pychevrons E, P = [ (5,7) , (3,1) , (3,4) , (3,2) ] , 10

\pychevrons initSac(E,P)

11
}

\hrulefill

\Par

Cela signifie que la valeur maximale des objets que l'on peut mettre dans le sac est égale à 11 ($7 + 4$, avec un poids de $5+3=8$).

\item \textit{Approche dynamique de type \og Bottom Up \fg}.
\Par

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/04-sac-a-dos-dyn.py}}}
\vspace*{-10pt}
\begin{listing}{}{04-sac-a-dos-dyn.py}\end{listing}

\Par

Avec cette approche, il n'y a plus de récursivité mais une itération.

On garde à peu près la même structure pour la fonction \texttt{sac}.

\Par

On obtient bien entendu le même résultat, à savoir \og 11 \fg.
\end{itemize}

\newpage

\item Comme nous pouvons le voir ici, ces solutions n'affichent que la valeur optimale. Le problème du sac à dos étant d'obtenir la combinaison des objets retenus, il nous faut compléter ces solutions.

Si on complète l'approche Bottom up, cela donne le programme suivant:\enlargethispage*{\baselineskip}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/04-sac-a-dos-bottomup.py}}}
\vspace*{-10pt}
\begin{listing}{}{04-sac-a-dos-bottomup.py} \end{listing}

\Par

Ici, on ajoute une liste \texttt{garde} qui stocke le numéro des objets que l'on met dans le sac.


\item Dans l'approche récursive initiale, la complexité est en $O\big(2^n\big)$. En effet, deux appels récursifs sont fait pour $n$ objets.

\Par


Dans l'approche Bottom Up, elle est en $O(n \times P)$ car il y a deux boucles imbriquées portant sur $n$ et $P$, et qu'il y a le même nombre d'opérations élémentaires dans chacune d'elles.

\begin{attention}
Il ne faut pas conclure que la complexité est linéaire par rapport à $P$. En effet, la variable \texttt{P} est de taille $\log_2(P)$ et on peut alors écrire que le poids maximal est $P = 2^{\log_2(\texttt{P})}$. La complexité du programme dynamique est alors exponentielle par rapport à la taille de \texttt{P}.

Cependant, elle reste meilleure que celle du programme initial.
\end{attention}
\end{questions}
