京都大学 情報学研究科 知能情報学専攻 2021年8月実施 情報学基礎 F2-1
Author
Isidore, 祭音Myyura
Description
Kai
設問1
The optimal value is \(16\), while there is 2 solutions
\[
\{a_5, a_3, a_2\} , \{a_5, a_4, a_1\}
\]
設問2
The output value is \(16\), while the output solution is
\[
\{a_5, a_3, a_2\}
\]
設問3
Design the Input like below
| \(a_1\) | \(a_2\) | |
|---|---|---|
| w | 1 | 10 |
| p | 2 | 10 |
| p/w | 2 | 1 |
Obviously, by comparing the value per weight, performing the algorithm defined in Q.2 will results in the output
\[
2,\{a_1\}
\]
However, the actual optimal value with solution is
\[
10, \{a_2\}
\]
which is 5 times better than the former algorithm.
設問4
\[
\begin{align}
\textrm{OPT}(1,1) = 0 \nonumber \\
\textrm{OPT}(2,4) = 4 \nonumber \\
\textrm{OPT}(3,5) = 8 \nonumber \\
\end{align}
\]
設問5
(1)
\[
\textrm{OPT}(i,0) = 0
\]
(2)
Denote the value of the first item \(a_1\) as \(p_1\), while weight as \(w_1\)
\[
\textrm{OPT}(1,j) = p_1
\]
(3)
Denote the value of the \(i\)-th item \(a_i\) as \(p_i\), while weight as \(w_i\)
\[
\textrm{OPT}(i,j) = \max\{\textrm{OPT}(i-1, j), \; p_i+\textrm{OPT}(i, j-w_i)\}
\]