\subsectionnn{Approche mathématique}
On passe en revue tous les objets $x_i$; si on met $x_i$ dans le sac alors la masse du contenu du sac augmente de $m_i$, sinon elle augmente de 0. On peut donc poser :
\[
\begin{cases}
\delta_i = 1 & \text{si $x_i$ est mis dans le sac},\\
\delta_i = 0 & \text{si $x_i$ n'est pas mis dans le sac}.
\end{cases}
\]
Ainsi, la masse totale des objets mis dans le sac est:
\[
\mu = \sum_{i=1}^{n}\delta_i m_i.
\]
Sur le même principe, la valeur totale $V$des objets mis dans le sac est:
\[
V = \sum_{i=1}^n \delta_iv_i.
\]

\subsectionnn{L'algorithme}

\begin{questions}
\item Le masse totale des objets doit être inférieure ou égale à $M$, d'où la première condition : $\mu \leqslant M$.

Il faut ensuite obtenir une valeur totale optimale, d'où la condition : $V$ optimale.

\item Un \og tri optimisé \fg est, dans notre problème, des objets
triés selon leur valeur (de la plus grande jusqu'à la plus petite), puis leur masse (de la plus petite jusqu'à la plus grande).

Trier les objets d'abord selon leur masse croissante n'est pas nécessairement un bon choix car les objets légers peuvent ne pas valoir cher.

\item L'algorithme doit parcourir tous les objets triés selon les critères mentionnés précédemment, ajoutés dans le sac tant que la masse totale ne dépasse pas $M$. On peut alors considérer l'algorithme page suivante.

\Par\enlargethispage*{3em}

\textit{Explications :}

\begin{itemize}
\item on parcourt toutes les valeurs de \texttt{m} et \texttt{v} (ligne 1);
\item Si la somme de la masse totale précédente et de la masse de l'objet sur lequel nous sommes est inférieure ou égale à la masse totale possible $M$ (ligne 2) alors on indique que l'on prend l'objet ($\delta_i=1$, ligne 3) en mettant \og 1 \fg{} dans le tableau des coefficients; sinon (ligne 6), on indique que l'on ne prend pas l'objet ($\delta_i=0$, ligne 7);
\item à la sortie de la boucle itérative, on a un tableau de la forme \linebreak\texttt{d = [1,1,0,1,0,1]} indiquant quels sont les objets à  mettre dans le sac à dos (objets correspondant aux nombres 1), ainsi que la masse totale (stockée dans la variable \texttt{MT}) et la valeur totale (\texttt{VT}).
\end{itemize}

\newpage

\begin{algorithme}{}
MT $\leftarrow$ 0 (masse totale du contenu du sac)
VT $\leftarrow$ 0 (valeur totale du contenu du sac)
m = tableau des masses des objets
v = tableau des valeurs des objets
d = tableau des coefficients
Pour i allant de 1 à n:\hfill(1)
\quad Si MT+m[i]$\leqslant$ M:\hfill(2)
\qquad d[i] $\leftarrow$ 1\hfill(3)
\qquad MT $\leftarrow$ MT + m[i]\hfill(4)
\qquad VT $\leftarrow$ VT + v[i]\hfill(5)
\quad Sinon:\hfill(6)
\qquad d[i] $\leftarrow$ 0\hfill(7)
\quad Fin du Si
Fin du Pour
\end{algorithme}
\end{questions}
