\documentclass[11pt]{article}
\usepackage{program}


\title{6.046 Problem Set 7}
\author{Chris Laas: Section G}
\date{April 4, 2000}

\pagestyle{myheadings}
\markright{Chris Laas: Section G \hfil 6.046J/18.410J \hfil 4/4/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}.}
\NumberProgramstrue
\def\RETURN{\keyword{return}\ }
\def\MOD{\mbox{mod}\ }
\def\text#1{\mbox{ #1 }}
\def\AND{\mbox{\bf\ and }}
\def\OR{\mbox{\bf\ or }}
\def\TRUE{\mbox{\bf true}}
\def\FALSE{\mbox{\bf false}}
\def\choice#1{\left\{ \begin{array}{ll} #1 \end{array} \right.}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}



\begin{document}
\maketitle






\section*{Problem 6-1}
\begin{enumerate}

\item%(a)

This problem is quite trivial: define $Y$ to be the elements of $X$,
sorted in nondecreasing order using a stable, $O(n^2)$ time sort.
Then we simply use the standard $|LCS-Length|$ and $|Print-LCS|$
algorithm to generate the longest monotonically increasing subsequence
(LMIS) of $X$.

\begin{program}
|LMIS-Length|(X)
\quad\tab \FOR i \gets 1 \rdots |Length|(X)
              Y[i] \gets X[i]
              \untab%
          |Insertion-Sort|(Y)
          \RETURN |LCS-Length|(X, Y)
\end{program}

The copying loop executes exactly $n$ times, and $|Insertion-Sort|$
and $|LCS-Length|$ are known to terminate; thus, this algorithm must
terminate.  The result is the $b$ and $c$ tables from $|LCS-Length|$,
which can be used to reconstruct the LMIS from $X$; also, the length
of the LMIS is equal to $c[n,n]$.  To prove correctness, assume that
the result is not a LMIS of $X$, i.e. there exists another, longer,
monotonically increasing subsequence of $X$.  Then this new
subsequence is also a subsequence of both $X$ and $Y$, and thus the
new subsequence is longer than that returned by $|LCS-Length|$; this
is impossible, by the correctness of $|LCS-Length|$.

Since the loop executes exactly $n$ times, $|Insertion-Sort|$ takes
$O(n^2)$ time, and $|LCS-Length|$ takes $O(n^2)$ time, this algorithm
takes $O(n^2)$ time.  The algorithm would be made faster by using a
faster stable sort than insertion sort, but this would not decrease
the asymptotic running time of the algorithm.

We simply use $|Print-LCS|(b, X, |Length|(X), |Length|(X))$ to
reconstruct the LMIS; this procedure takes $O(n+n) = O(n)$ time.


\item%(b)

There is an optimal substructure theorem for three sequences roughly
equivalent to that for two sequences: let $X[1 \rdots l]$,
$Y[1 \rdots m]$, and $Z[1 \rdots n]$ be sequences, and let
$W[1 \rdots k]$ be any LCS of $X$, $Y$, and $Z$.
\begin{enumerate}
\item%1
If $x_l = y_m = z_n$, then $w_k = x_l = y_m = z_n$ and $W_{k-1}$ is an
LCS of $X_{l-1}$, $Y_{m-1}$, and $Z_{n-1}$.
\item%2
If $x_l \neq y_m \OR x_l \neq z_n$, then $w_k \neq x_l$ implies that
$W$ is an LCS of $X_{l-1}$, $Y$, and $Z$.
\item%3
If $y_m \neq x_l \OR y_m \neq z_n$, then $w_k \neq y_m$ implies that
$W$ is an LCS of $X$, $Y_{m-1}$, and $Z$.
\item%4
If $z_n \neq x_l \OR z_n \neq y_m$, then $w_k \neq z_n$ implies that
$W$ is an LCS of $X$, $Y$, and $Z_{n-1}$.
\end{enumerate}

The proof follows exactly as that for two sequences.  This optimal
substructure gives us the following recursion for the length of the
LCS of $X_i$, $Y_j$, $Z_k$:

$$
c[i,j,k] = \choice{
  0   & \IF i = 0 \OR j = 0 \OR k = 0 \\
  c[i-1,j-1,k-1] + 1 
      & \IF i, j, k > 0 \AND x_i = y_j = z_k \\
  \max(c[i-1,j,k], c[i,j-1,k], c[i,j,k-1])
      & \IF i, j, k > 0 \AND \NOT (x_i = y_j = z_k) \\
}
$$

Using the recursion formula, it's easy to write an $O(lmn)$-time
$Tri-LCS-Length$ based on the standard $LCS-Length$ algorithm.

\begin{program}
|Tri-LCS-Length|(X, Y, Z)
\quad\tab l \gets |Length|(X)
          m \gets |Length|(Y)
          n \gets |Length|(Z)
          \FOR i \gets 0 \rdots l
              \FOR j \gets 0 \rdots m
                  c[i,j,0] \gets 0
                  \untab%
              \untab%
          \FOR i \gets 0 \rdots l
              \FOR k \gets 0 \rdots n
                  c[i,0,k] \gets 0
                  \untab%
              \untab%
          \FOR j \gets 0 \rdots m
              \FOR k \gets 0 \rdots n
                  c[0,j,k] \gets 0
                  \untab%
              \untab%
          \FOR i \gets 1 \rdots l
              \FOR j \gets 1 \rdots m
                  \FOR k \gets 1 \rdots n
                      \IF x_i = y_j \AND y_j = z_k
                         \THEN c[i,j,k] \gets c[i-1,j-1,k-1] + 1
                         \ELSE c[i,j,k] \gets \max(c[i-1,j,k], c[i,j-1,k], c[i,j,k-1])
                              \untab%
                         \untab%
                      \untab%
                  \untab%
              \untab%
          \RETURN c
\end{program}

The length of the LCS is given by $c[l,m,n]$.  Termination is
guaranteed by the explicit range of each FOR loop; the main loop must
finish after exactly $lmn$ iterations of the inner loop body.
Correctness is guaranteed by the optimal substructure of the LCS
problem.  The LCS can be reconstructed from the three-dimensional
array $c$, in a manner analagous to that described on page 319 of
CLR.

The first three loops take $O(lm)$, $O(ln)$, and $O(mn)$ time,
respectively; the main loop takes $O(lmn)$ iterations of the inner
loop to complete, and the inner loop executes in $O(1)$ time.  Thus,
this algorithm executes in $O(lmn)$ time.  The algorithm also takes
$O(lmn)$ space, and the LCS can be reconstructed in $O(l+m+n)$ time.


\end{enumerate}
\newpage






\section*{Problem 6-2}
\begin{enumerate}

\item%(a)

Each boy can only propose at most $n$ times, since there are $n$ girls
and each one can only be proposed to by him once.  Since there are $n$
boys and each can only be considered at most $n$ times before being
engaged, the process (inner loop) is executed at most $n^2$ times.
Thus the algorithm terminates and outputs a marriage.

Put another way, assume that the algorithm doesn't terminate.  After
$n^2$ iterations, then every boy and every girl have been tested
against each other.  Since girls never become unengaged, all girls
should be attached by now, and thus every boy is attached.  Thus
everyone is engaged, and the algorithm should terminate (contradicting
the assumption that the algorithm doesn't terminate).  And, if we know
that the algorithm terminates, we know that all boys are engaged;
thus, since there are an equal number of boys and girls, all girls are
engaged, and the algorithm outputs a marriage.


\item%(b)

Assume that the marriage is unstable.  Then there is a pair of a girl
and a boy (Alice and Bob) such that Bob prefers Alice to his fianc\'ee
(Carol) and Alice prefers Bob to her fianc\'e (Dave).  But when Bob
originally got engaged to Carol, Carol was the most desirable girl on
the list who had not already rejected him, so Alice had already
rejected Bob.  That would mean that Eddy, the person who Alice had
been engaged to at the time, was equally or more desirable to Alice
than Bob.  But that would mean that Dave (who is either also named
Eddy or is more desirable to Alice than Eddy) is equally or more
desirable to Alice than Bob, which contradicts the fact that Alice and
Bob are a dissatisfied pair.  Thus we have a contradiction if the
marriage is unstable.  Thus, the marriage produced is stable.


\item%(c)

Here's the counterexample.  There are two girls, Alice and Carol, and
two boys, Bob and Dave.  Their preference lists are given by:

\begin{tabular}{l|ll}
Name   &  1st choice  &  2nd choice \\
\hline
Alice  &  Bob    &  Dave  \\
Carol  &  Dave   &  Bob   \\
Bob    &  Carol  &  Alice  \\
Dave   &  Alice  &  Carol  \\
\end{tabular}

In algorithm (a), let's say we start with Bob.  Bob proposes to Carol,
who accepts.  Then Dave proposes to Alice, who accepts.

In algorithm (b), let's say we start with Alice.  Alice proposes to
Bob, who accepts.  Then Carol proposes to Dave, who accepts.  This
marriage is different from the result of algorithm (a).



\end{enumerate}
\newpage







\section*{Problem 6-3}
\begin{enumerate}

\item%(a)

True.  Proof:  Take any minimal sequence $M$; we will construct a
minimal sequence $M'$ which fulfills this property.

First, we ask by which rule $s_1$ is deleted in $M$.  If $s_1$ is
deleted alone in $M$, then we can let $M'$ be equal to $M$, but with
the move that deletes $s_1$ moved to the beginning (this is legal,
since we don't have to arrange for $s_1$ to be next to another
character, and deleting $s_1$ earlier will not prevent any other moves
from being made).  Then $M'$ will also be a minimal sequence, as
desired.  Also, the subsequent $n-1$ moves which erase $S'$ will be a
minimal sequence for $S'$, since if they were not, we could construct
a shorter sequence for $S$ by taking a minimal sequence for $S'$ and
prepending the move that deletes $s_1$.  Thus, in conclusion, if $s_1$
is deleted alone in $M$, we can construct a minimal sequence $M'$
which fulfills case 1 of the property.

Now, we take the case that $s_1$ is deleted along with a ``buddy'' in
$M$, at some point.  Then, if we call the buddy $s_l$ in its position
in the original string $S$, it's clear that $s_1 = s_l$.  Now, let us
construct $M'$ as equal to $M$, except that any moves, occurring
before $s_1$ and $s_l$ are deleted, which delete characters in
$S'' = s_{l+1} \dots s_u$, should be shifted forward to occur {\em
after} $s_1$ and $s_l$ are deleted together.  This is legal, because
(a) any moves before $s_1$ and $s_l$ cannot involve characters from
both $S'$ and $S''$, since $s_l$ separates them, and (b) the deletion
of $s_1$ and $s_l$ certainly could not depend on deletions from $S''$,
since the characters in $S''$ are not between $s_1$ and $s_l$.  Of
course, all the characters in $S'$ must be deleted by $M'$
{\em before} $s_1$ and $s_l$ are deleted, since they are in between.
Thus, we can say that $M'$ consists of an initial sequence of moves which
deletes all the elements of $S'$ and nothing but elements of $S'$,
then a move which deletes $s_1$ and $s_l$ together, and then a final
sequence of moves which deletes all the remaining elements, i.e. all
the elements of $S''$.  By the obvious argument (contradiction by
construction of shorter sequences), the subsequences of $M'$ which
delete $S'$ and $S''$ must be minimal sequences for $S'$ and $S''$.
Thus, in conclusion, if $s_1$ is not deleted alone in $M$, we can
construct a minimal sequence $M'$ which fulfills case 2 of the
property.

Thus, in either case, the desired property is satisifed by our
constructed minimal sequence for $S$.  Thus the existence of such a
sequence is proven.


\item%(b)

False.  As a counterexample, let us take $S = ``aba''$.  There is a
minimal sequence M which deletes ``b'' alone as the first move and
``aa'' together as the second move.  However, there is no minimal
sequence which deletes ``b'' as the second move.


\item%(c)

False, by the same counterexample.  If $S = ``aba''$, there is a
minimal sequence which deletes ``b'' alone as the first move and
``aa'' together as the second move.  However, since ``delete the first
character, then delete the second character, then delete the third
character'' is not a minimal sequence, there is no minimal sequence
which fulfills the condition.


\item%(d)

True; this follows directly from the truth of proposition (a).

We certainly can construct a sequence $M$ with length $p_{i,j}(S)$.
For, we can construct a sequence $M_i$ by deleting $s_i$ and recursing
on $i+1,j$ to generate a subsequence with length $p_{i+1,j}(S)$: then
$M_i$ will have length $1 + p_{i+1,j}(S)$.  And, for any
$i < l \leq j$ such that $s_i = s_l$, we can construct a sequence
$M_l$ by first recursing on $i+1,l-1$ to delete the initial
subsequence, then deleting $s_i$ and $s_l$ together, then recursing on
$l+1,j$ to delete the final subsequence: then $M_l$ will have length
$1 + p_{i+1,l-1}(S) + p_{l+1,j}(S)$.  Hence, by taking the sequence
(among $M_i$ and all the $M_l$'s) with minimum length, we can create a
sequence with length
$\min(1+p_{i+1,j}(S),
   \min_{i < l \leq j, s_i = s_l} \{ 1 + p_{i+1,l-1}(S) + p_{l+1,j}(S) \})$.
Thus any minimal sequence for $S$ will have to be that length or
shorter.

Conversely, we can show (by induction) that any minimal sequence for
$S$ is at least that long.  (The base case is given by $p_{i,j}(S) = 0$
for $j < i$.)  For, by proposition (a), there exists a minimal
sequence $M$ such that either: case 1 holds, in which case the length
of $M$ is greater than or equal to $1+p_{i+1,j}(S)$; or, case 2 holds,
in which case the length of $M$ is greater than or equal to
$1 + p_{i+1,l-1}(S) + p_{l+1,j}(S)$, for some $i < l \leq j$ such that
$s_i = s_l$.

Thus, since we have shown that any minimal sequence must be both
greater than or equal to and less than or equal to the expression
$\min(1+p_{i+1,j}(S),
   \min_{i < l \leq j, s_i = s_l} \{ 1 + p_{i+1,l-1}(S) + p_{l+1,j}(S) \})$,
we have proven that
$$
p_{i,j}(S) =
 \min(1+p_{i+1,j}(S),
    \min_{i < l \leq j, s_i = s_l} \{ 1 + p_{i+1,l-1}(S) + p_{l+1,j}(S)\})
$$


\end{enumerate}
\newpage







\section*{Problem 6-4}

The same algorithm we developed for finding a minimal spanning tree
will work here.  This is because we have an analogous theorem to
theorem 24.1 of CLR.  First, terminology: a minimized-maximum spanning
tree (MMST) will be a spanning tree for $G$ such that the weight of
the maximum-weight edge in the spanning tree is minimized.  The
``weight'' of a set $A$ of edges will be defined as
$w(A) = \max \{ w(x,y) \text{for all} (x,y) \in A \}$.  (This also
gives the recursive formulation $w(A) = \max(w(A-\{(x,y)\}), w(x,y))$
for any $(x,y) \in A$, with the weight of the empty set as zero.)
With this definition, we see that an MMST is a spanning tree $T$ which
minimizes $w(T)$.

This is the theorem:  let $G = (V,E)$ be a connected, undirected graph
with a real-valued weight function $w$ defined on $E$.  Let $A$ be a
subset of $E$ that is included in some minimized-maximum spanning tree
for $G$, let $(S, V-S)$ be any cut of $G$ that respects $A$, and let
$(u,v)$ be a light edge crossing $(S, V-S)$.  Then, the set
$A' = A \union \{(u,v)\}$ is contained in a minimized-maximum spanning
tree for $G$.

The proof is parallel to that for theorem 24.1 on pages 501-502.  The
only difference is that we must show that $w(u,v) \leq w(x,y)$ implies
that $w(T') \leq w(T)$, for $T' = T - \{(x,y)\} \union \{(u,v)\}$.
This is fairly trivial:

\begin{eqnarray*}
w(T') & =    & \max(w(T' - \{(u,v)\}), w(u,v)) \\
      & =    & \max(w(T  - \{(x,y)\}), w(u,v)) \\
      & \leq & \max(w(T' - \{(x,y)\}), w(x,y)) \\
      & =    & w(T) \\
\end{eqnarray*}

The rest of the proof is identical, substituting ``minimized-maximum
spanning tree'' for ``minimum spanning tree''.

Now, given that a parallel version of theorem 24.1 is true for MMSTs,
we know that any minimum-spanning-tree algorithm based on it produces
MSTs which are also MMSTs.  Thus, we can just pick our favorite MST
generating algorithm; for example, we could use $|MST-Kruskal|$ (which
runs in $O(E \lg E)$ time) or $|MST-Prim|$ (which can be implemented
to run in $O(E + V \lg V)$ time).  (The algorithm we developed in
class appears to be Prim's.)  The MSTs generated by these algorithms
will also be MMSTs.

\newpage







\section*{Problem 6-5}
\begin{enumerate}

\item%(a)


The objects numbered $i_1, i_2, \dots, i_k$ (with
$i_1 < i_2 < \dots < i_k$) is a subset of the $n$
items that fits exactly into a knapsack of size $M$ if and only if
the objects numbered $i_1, i_2, \dots, i_{k-1}$ is a subset of the
$i_k - 1$ first items that fits exactly into a knapsack of size
$M-i_k$.  This gives a natural recursive formula for the boolean
function $e(i,M)$ which tells whether there exists a subset of the
first $i$ items that fits exactly into a knapsack of size $M$:

$$
e(i,M) = \choice{
\FALSE                        & \IF M < 0 \\
\TRUE                         & \IF M = 0 \\
\FALSE                        & \IF M > 0 \AND i = 0 \\
e(i-1,M) \OR e(i-1,M-m_i)     & \IF M > 0 \AND i > 0 \\
}
$$

The first clause means that no set of items can fit in a knapsack of
negative size.  The second means that the empty set (a subset of any
set) fits exactly into a knapsack of size zero.  The third means that
the empty set does not fit exactly into a knapsack of positive size.
The fourth is the recursive part:  there exists a subset of the first
$i$ items that fits exactly into a knapsack of size $M$ if and only if
either there exists a subset of the first $i-1$ items that fits
exactly into a knapsack of size $M$ (in which case the new subset does
not include item $i$), or there exists a subset of the first $i-1$
items that fits exactly into a knapsack of size $M-m_i$ (in which case
the new subset does include item $i$).

This recursion can easily be converted into a dynamic programming
algorithm:

\vbox{
\begin{program}
|Exact-Fit-Exists|(m[1 \rdots n], M)
\quad\tab \FOR i \gets 0 \rdots n
              e[i,0] \gets \TRUE
              \untab%
          \FOR J \gets 1 \rdots M
              e[0,J] \gets \FALSE
              \untab%
          \FOR i \gets 1 \rdots n
              \FOR J \gets 1 \rdots M
                  \IF J \geq m[i]
                     \THEN e[i,J] \gets e[i-1,J] \OR e[i-1,J-m[i]]
                     \ELSE e[i,J] \gets e[i-1,J]
                          \untab%
                     \untab%
                  \untab%
              \untab%
          \RETURN e[n,M]
\end{program}
}

The algorithm must terminate, since each FOR loop is bounded by a
finite range.  The algorithm is clearly correct, since it reproduces
the recursion formula exactly (the IF statement accounts for the
$M < 0$ case).  Since the main loop's inner loop body is executed
exactly $nM$ times, the algorithm's run time is $O(nM)$.


\item%(b)

We notice that the formula for $e[i,J]$ does not use any element of
$e$ with first index less than $i-1$; thus, the algorithm is only ever
using 2 rows at a time.  Thus, we can get away with simply maintaining
the ``previous row'' $p$ and the ``current row'' $q$.

\begin{program}
|Exact-Fit-Exists-Using-Less-Space|(m[1 \rdots n], M)
\quad\tab p[0] \gets \TRUE
          \FOR J \gets 1 \rdots M
              p[J] \gets \FALSE
              \untab%
          \FOR i \gets 1 \rdots n
              \FOR J \gets 1 \rdots M
                  \IF J \geq m[i]
                     \THEN q[J] \gets p[J] \OR p[J-m[i]]
                     \ELSE q[J] \gets p[J]
                          \untab%
                     \untab%
                  \untab%
              \FOR J \gets 1 \rdots M
                  p[J] \gets q[J]
                  \untab%
              \untab%
          \RETURN q[M]
\end{program}

The algorithm is functionally equivalent to the previous one, so the
analysis for termination, correctness, and runtime are the same.  The
only difference is that the $O(nM)$ space structure $e[i,J]$ has been
eliminated, and replaced with the two $O(M)$ space arrays $p[J]$ and
$q[J]$.


\item%(c)

Given the matrix $e[i,J]$ generated by the algorithm in (a), we can
print out the subset with this algorithm (which should be called as
$|Print-Exact-Fit|(m, n, M, e)$):

\begin{program}
|Print-Exact-Fit|(m[1 \rdots n], i, M, e[1 \rdots n, 1 \rdots M])
\quad\tab \IF M > 0
             \THEN \IF e[i-1,M-m[i]]
                      \THEN |Print-Exact-Fit|(m, i-1, M-m[i], e)
                            |Print|(i)
                      \ELSE |Print-Exact-Fit|(m, i-1, M,      e)
\end{program}

The precondition for the algorithm is that $e[i,M]$ is true.  Thus it
is the case that either $M = 0$, $e[i-1,M-m[i]]$ is true, or
$e[i-1,M]$ is true.  If $M = 0$, then the subset to be printed is the
empty set, so we return.  If $e[i-1,M-m[i]]$ is true, then there
exists a matching subset which consists of the union of a subset of
the first $i-1$ items which fit exactly into a knapsack of size
$M-m[i]$, which we recurse to print out, and item $i$, which we then
print out.  Else, $e[i-1,M]$ is true, so there exists a matching
subset which is a subset of the first $i-1$ items, which we recurse on
to print out.  In each of the recursive calls, the precondition is
satisfied.  Thus, the algorithm is correct.

The algorithm must terminate because $i$ decreases with every
recursive call, and due to the structure of $e$ (defined by the
algorithm in (a)), $i$ cannot go below zero before $M$ reaches zero.

This algorithm runs in $O(n)$ time, since $i$, which starts at $n$,
decreases with every iteration and never goes below zero.

It is not possible to maintain the $O(M)$ space bound, unfortunately,
because the information needed to reconstruct the subset is in all of
the rows of the structure $e$, which uses $O(nM)$ space.

\item%(d)

The most likely-seeming greedy algorithm would be to choose the item
$i$ such that $m_i \leq M$ and that $\frac{v_i}{m_i}$ is maximized
(most ``bang for the buck'').  Then, we put as many of item $i$ in the
knapsack as will fit.  If there remains any space in the knapsack,
repeat the procedure with $M$ as the remaining space in the knapsack.
In pseudocode:

\begin{program}
|Greedy-Thief|(m[1 \rdots n], v[1 \rdots n], M)
\quad\tab \mbox{If there is no $i$ such that $m[i] \leq M$, return.}
          \mbox{Out of the set $\{i \text{such that} m[i] \leq M\}$, pick $i$ such that $\frac{v[i]}{m[i]}$ is maximized.}
          \mbox{Take $k = \lfloor\frac{M}{m[i]}\rfloor$ of item type $i$.}
          \mbox{Continue: $|Greedy-Thief|(m, v, M - k m[i])$}
\end{program}

This algorithm must always terminate, because $M$ decreases
monotonically at each recursion, and never goes below zero.  Finding
$i$ such that $m[i] \leq M$ and $\frac{v_i}{m_i}$ is maximized takes
$O(n)$ steps, each time the operation is performed; an upper bound on
the number of times the operation is performed is $O(\lg M)$, since
$M$ decreases by at least $\lceil\frac{M}{2}\rceil$ at each recursion.
Thus, the run time of this algorithm is bounded by $O(n \lg M)$.

However, the output of this algorithm is not always optimal.  Consider
the case $m[1] = 2$, $v[1] = 10$, $m[2] = 3$, $v[2] = 11$, and
$M = 7$.  The greedy thief will first take as many of item 1 as he
can (3), using up 6 spaces; he then won't have room to fit anything
else in, so his total value will be 30.  On the other hand, the
optimal solution would be to take two of item 1, and one of item 2,
using up all 7 spaces, and giving a total value of 31.


\item%(e)

For any knapsack size $M$, we need to find the optimal number $k$ of
items to take of the optimal item type $i$.  We do this by finding the
pair $(k,i)$ such that $1 \leq i \leq n$, $0 < k m[i] \leq M$, and the
total value $k v[i] + V[M - k m[i]]$ is maximized.  (The value V[M] is
defined as this maximum value.)  This directly gives us the needed
dynamic programming, in which we maintain the three $M$-element arrays
$K[1 \rdots M]$, $I[1 \rdots M]$, and $V[1 \rdots M]$:

\vbox{
\begin{program}
|Optimal-Thief|(m[1 \rdots n], v[1 \rdots n], M)
\quad\tab K[0] \gets 0
          V[0] \gets 0
          \FOR J \gets 1 \rdots M
              K[J] \gets 0
              V[J] \gets 0
              \FOR i \gets 1 \rdots n
                  \FOR k \gets 1 \rdots \lfloor\frac{J}{m[i]}\rfloor
                      \IF k v[i] + V[J - k m[i]] > V[J]
                         \THEN V[J] \gets k v[i] + V[J - k m[i]]
                               I[J] \gets i
                               K[J] \gets k
                               \untab%
                         \untab%
                  \untab%
              \untab%
          \untab%
          \RETURN (K, I, V)
\end{program}
}

The optimal value is returned in $V[M]$.

This algorithm must terminate, since all FOR loops are bounded by
finite ranges (assuming, of course, that $m[i]$ are all nonzero).

The algorithm is correct because of the optimal substructure of the
problem.  For any $J$, we maximize $V[J]$ by considering the effect of
taking $k$ items of item type $i$, for all valid $k$ and $i$: we
consider both the value of those items, and the maximum possible value
of the items we can fit in the rest of the knapsack.

Since $J \leq M$ and $m[i] \geq 1$, the innermost loop body executes
at most $M$ times per iteration of the next-innermost loop body.  That
one iterates exactly $n$ times per iteration of the outer loop, which
iterates exactly $M$ times.  Hence, multiplying gives us an upper
bound of $O(n M^2)$ iterations of the inner loop body; since the inner
loop body executes in $O(1)$ time, the run time of the algorithm is
$O(n M^2)$.  Since the storage used by the algorithm (discounting the
scalars $J$, $i$, and $k$) is the three arrays $K$, $I$, and $V$, each
of which have $M$ elements, the space requirement of the algorithm is
$O(M)$.

The optimal subset can be reconstructed from $K$ and $I$ in
$O(M)$ time by the following simple algorithm:

\vbox{
\begin{program}
|Print-Optimal-Subset|(m[1 \rdots n], M, K[1 \rdots M], I[1 \rdots M])
\quad\tab \IF K[M] \neq 0
             \THEN |Print|(\mbox{``take $K[M]$ of item type $I[M]$''})
                   |Print-Optimal-Subset|(m, M - K[M] m[I[M]], K, I)
\end{program}
}

\end{enumerate}
\newpage



\end{document}
