this is for holding javascript data
Mazdak Farrokhzad edited c) Imposing a restriction.tex
about 10 years ago
Commit id: 5c4a09edb7aa01a62bf74189aa02836eed668e86
deletions | additions
diff --git a/c) Imposing a restriction.tex b/c) Imposing a restriction.tex
index 3be8046..f085a1c 100644
--- a/c) Imposing a restriction.tex
+++ b/c) Imposing a restriction.tex
...
\section{c) Imposing a restriction}
One possible restriction would be to limit the amount possible to invest in each company to a constant amount $c$, so that the choice of how much to invest in a specific company instead becomes a choice of whether to invest money in the company or not. This makes the problem equivalent to the 0/1 knapsack.
In this case, the algorithm becomes:
\begin{verbatim}
function maxReturn(i, x) begin
initialise mem[0..i, 0..x] to -1
return mr(i, x)
end
function mr(i, x) begin
if mem[i, x] != -1 then
if i = 0 then
let mem[i, x] = 0
end
let mem[i, x] = max(mr(i - 1, x), g(i, c) + mr(i - 1, x - c))
end
return mem[i, x]
end
\end{verbatim}
\begin{algorithm}[H]
\caption{Computes the maximum return of investing $x$ dollars in $i$ companies Input: $i$ is the set of companies or the index of the last element, $x$ is the amount of dollars available for investment. Uses dynamic programming.
\label{alg:max-return-dp}}
\begin{algorithmic}[1]
\Function{maxReturn}{$i, x$}
\Let{$mem$}{$matrix[i, x]$ with each element to $-1$}
\Return{$\Call{mr}{i, x}$}
\EndFunction
\Statex
\Function{mr}{$i, x$}
\If{$mem[i,x] \neq -1$}
\If{$i = 0$}
\Let{$mem[i,x]$}{$0$}
\EndIf
\Let{$mem[i,x]$}{$max[mr(i - 1, x), g(i, c) + mr(i - 1, x - c)]$}
\EndIf
\Return{$mem[i,x]$}
\EndFunction
\end{algorithmic}
\end{algorithm}