diff options
| -rw-r--r-- | assignment11.tex | 32 |
1 files changed, 29 insertions, 3 deletions
diff --git a/assignment11.tex b/assignment11.tex index 2bc18bd..eec7ccb 100644 --- a/assignment11.tex +++ b/assignment11.tex @@ -25,6 +25,7 @@ \usepackage{caption} \usepackage[hidelinks]{hyperref} \usepackage{url} +\usepackage{minted} \parindent0pt @@ -71,9 +72,34 @@ Sorting takes $\pazocal O(n\log n)$, iterating the array $\pazocal O(n)$, so this algorithm uses $\pazocal O(n\log n)$. \item \begin{enumerate} - \item %todo - - \item %todo + \item Define $m(i,w)$ as the maximum value we can reach with a maximum weight of $w$ and only using items $1$ to $i$. We can compute it using the following recurrence: + + \begin{equation*} + m(i,w) = \begin{cases} + 0 & \text{if $i=0$} \\ + m(i-1, w) & \text{if $w_i>w$} \\ + \max(m(i-1, w), m(i-1,w-w_i) + v_i) & \text{otherwise} + \end{cases} + \end{equation*} + + In the first case we cannot use any item, so obviously the maximum value is $0$. In the second case, item $w_i$ is heavier than the maximum weight, so the only possibility is to not use it. Therefore this case reduces to $m(i-1,w)$. In the last case we both consider the possibility of using item $i$ and of not using it. + + The solution to the problem is then $m(n,W)$. We can use a $n\times W$ matrix to store $m(i,w)$ for all $0\le i\le n, 0\le w\le W$. If we fill it starting with $i=0$, in all three cases we can use values we already computed. Computing the maximum of two numbers takes constant time, so the complexity of this algorithm is the complexity of filling the matrix, which is $\pazocal O(nW)$. + + \item Assume we already have our table with values of $m$. We can read it from $m(n,W)$ to the top left, and trace back what recurrence we used. Only when $m(i,w)=m(i-1,w-w_i)+v_i$ was applied, we need to output $i$. + + \begin{minted}[linenos,tabsize=0,xleftmargin=20pt,fontsize=\footnotesize]{python} + i, j = n, W + while m[i][j] != 0: + if m[i-1][j] == m[i][j]: + i = i - 1 + else: + print(i - 1) + i = i - 1 + j = j - w[i] + \end{minted} + + In every step we decrease $i$, so this takes $\pazocal O(n)$. \end{enumerate} |