# Knapsack problem

## Definition

We assume that the there is a knapsack with a volume $b>=0$, and a set of items with which the kanpsack is filled. Every item has it's own volume $a_j>=0$ and value $c_j>=0$.
The goal is to fill the most valuable knapsack so that the sum of all items inside is the maximum possible, without going over the knapsack's volume.

The following definition is given for the **Unbounded Knapsack problem (UKP)** which places no upper bound on the number of copies of each kind of item and can be formulated as below except for that the only restriction is that the number of items in the solution must be non-negative integers.



\begin{equation}
max\sum_{j=1}^n c_jx_j\\
\sum_{j=1}^n a_jx_j \le b\\
x_1,x_2,...,x_n \in Z,\; x_j\ge0
\end{equation}


A more common occurence of this problem is in a form of **0-1 Knapsack Problem**, which restricts the number of copies of one kind of item to zero or one $x_j\in\{0,1\}$.

## Applications

The name "knapsack problem" dates back to the early works of the mathematician Tobias Dantzig (1884–1956), and refers to the commonplace problem of packing the most valuable or useful items without overloading the luggage.



Knapsack problem (KP) has broad applications in different fields such as
machine scheduling, space allocation, and asset optimization. Meanwhile, it is a hard
problem due to its computational complexity, but numerous solution approaches have
been developed for a variety of KP. 

The problem often arises in resource allocation where the decision makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively. Problems like these arise in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios, and generating keys for the Merkle–Hellman and other knapsack cryptosystems.



## Solution

### Recursive solution
- The problem is solved by dividing it into stages
- We are introducing a helper function $F$ defined like following which we will solve with the recursive formulas below:
$F_k=max\{c_1 x_1 + ... + c_k x_k \:|\: a_1 x_1 + ... + a_k x_k \le y,\;x_1,...,x_k\ge0,\;x_1,...,x_k\in Z\}$

#### Backward solution:
We need to rememer all the steps of the solution in order to reach the final solution.
<ul>
    <li>$F_1(y)=c_1\lfloor\frac{y}{a_1}\rfloor$</li>
    <li>$F_k(y)=max\{F_{k-1}(y - a_k x_k) + c_k x_k \:|\: x_k \in \{0,1,...,\lfloor \frac{y}{a_k}\rfloor\}\},\; k\ge2$</li>
</ul>

#### Forward solution:
Eeasier to implement in computers and in comparison to the Backward solution only the last two rows of the table are need to be stored in memory.
<ul>
    For forming of the k\y table
    <li>$F_k(y)=-\infty,\;y<0$</li>
    <li>$F_1(y)=c_1\lfloor\frac{y}{a_1}\rfloor,\;y\ge0$</li>
    <li>$F_k(y)=max\{F_{k-1}(y), F_{k}(y - a_k) + c_k\},\; k\ge2$</li>
</ul>
<ul>
    <li>
        This will store the highest index $j$ such that the $j$ variable in the optimal solution in F_k(y) is positive. If the optimal solution in $F_k(y)$ is $0$ we define this index $i$ with $0$.
    <br>For forming of the i\y table<br>
    $
        i_k(y)=
        \begin{cases}
        i_{k-1}(y)\quad &,c_k+F_k(y)<F_{k-1}\\
        k\quad &,c_k+F_k(y)\ge F_{k-1}\\
        \end{cases}
        ,\qquad
        i_1(y)=
        \begin{cases}
        0\quad &,F_{1}(y)=0\\
        1\quad &,F_{1}(y)\ne 0\\
        \end{cases}
    $
    </li>
    <li>
    We can reconstruct the optimal solution from the value reached for $i_n(y)$, by using the index and the corresponding values $i_n(b)$ and $i_n(b-a_{i_n(b)})$.
    $
        i_n(y)=
        \begin{cases}
        k &,x_n=1,n=k\\
        \ne k &,x_n=0,n\ne k\\
        \end{cases}\\
        i_n(b-a_{i_n(b)})=
        \begin{cases}
        k\quad &,x_k\ge a_{i_n(b)}, \text{testing for}\; y-a_{i_n(b)}\\
        e\quad &,x_e=1,x_{e+1}=0,x_k=1\\
        \end{cases}
    $
    </li>
</ul>


## Examples

### Example 1
\begin{equation}
max\;6x_1+7x_2+10x_3+4x_4+5x_5\\
3x_1+4x_2+5x_3+2x_4+2x_5\le9\\
x\in Z
\end{equation}

##### Forward solution
First we determine the capacities: $c_1=6, c_2=7, c_3=10, c_4=4, c_5=5, a_1=3, a_2=4 ,a_3=5, a_4=2, a_5=2$  
Now we can form our tables $F_k(y)$ and $i_k(y)$ using the formulas from above to find $F_{max}$ and our optimum strategy for $x=(0,0,0,0,0)$:  
<table>
<tr><td>

| k\y | 0 | 1 | 2 | 3 |  4 |  5 |  6 |  7 |  8 |  9 |
|:---:|:-:|:-:|:-:|:-:|:--:|:--:|:--:|:--:|:--:|:--:|
|  1  | 0 | 0 | 0 | 6 |  6 |  6 | 12 | 12 | 12 | 18 |
|  2  | 0 | 0 | 0 | 6 |  7 |  7 | 12 | 13 | 14 | 18 |
|  3  | 0 | 0 | 0 | 6 |  7 | 10 | 12 | 13 | 16 | 18 |
|  3  | 0 | 0 | 4 | 6 |  8 | 10 | 12 | 14 | 16 | 18 |
|  5  | 0 | 0 | 5 | 6 | 10 | 11 | 15 | 16 | 20 | 21 |

</td>
<td>&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;</td>
<td>
    
| i\y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|:---:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|  1  | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
|  2  | 0 | 0 | 0 | 1 | 2 | 2 | 1 | 2 | 2 | 1 |
|  3  | 0 | 0 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 1 |
|  3  | 0 | 0 | 4 | 1 | 4 | 3 | 1 | 4 | 3 | 1 |
|  5  | 0 | 0 | 5 | 1 | 5 | 5 | 5 | 5 | 5 | 5 |

</td></tr> </table>
Finally, we can see that the maximum is reached for $F_5(9)=21 \rightarrow F_{max}=21$<br>
Now we need to form the maximum packing strategy.<br>
We look in the $i$ table to see what item (index) corresponds to the maximum in $F_5(9)$<br> 
$i_5(9)=5$ we add $1$ to the corresponding position in our $x=(0,0,0,0,0) \rightarrow x=(0,0,0,0,1)$ <br>
<ol>
<li> $i_5(9-a_5)=i_5(9-2)=i_5(7)=5$, we add $1$ to the corresponding position in our $x=(0,0,0,0,1) \rightarrow x=(0,0,0,0,2)$ </li><br>
<li> $i_5(7-a_5)=i_5(7-2)=i_5(5)=5$, we add $1$ to the corresponding position in our $x=(0,0,0,0,2) \rightarrow x=(0,0,0,0,3)$ </li><br>
<li> $i_5(5-a_5)=i_5(5-2)=i_5(3)=1$, we add $1$ to the corresponding position in our $x=(0,0,0,0,3) \rightarrow x=(1,0,0,0,3)$ </li><br>
<li> $i_5(3-a_5)=i_5(3-2)=i_5(1)=0 \rightarrow$ we finished filling the solution.</li><br>
</ol>
Maximum solution: $F_{max}=21,\;x=(1,0,0,0,3)$

##### Backward solution
We form the general formula formula for the maximum possible set:
<br>

$$
\begin{aligned}
F_5(9)&=max\{5x_5+F_4(9-2x_5)|x_5\in \{0,1,2,3,4\}\}  \\
       &=max\{F_4(9), F_4(7)+5, F_4(5)+10, F_4(3)+15, F_4(1)+20\}\\
       &\qquad\quad(1)\qquad\quad(2)\qquad\quad(3)\quad\qquad(4)\quad\qquad(5)\\
\end{aligned}
\\
-----------------------
\\
\begin{aligned}
(1)\quad F_4(9)&=max\{4x_4+F_3(9-2x_4)\;|\;x_4\in \{0,1,2,3,4\}\}  \\
          &=max\{F_3(9), F_3(7)+4, F_3(5)+8, F_3(3)+12, F_3(1)+16\} \\
          &\qquad\quad(1.1)\qquad(1.2)\qquad(1.3)\qquad(1.4)\qquad(1.5)\\
\end{aligned}\\
\begin{aligned}
(2)\quad F_4(7)&=max\{4x_4+F_3(7-2x_4)\;|\;x_4\in \{0,1,2,3\}\}  \\
          &=max\{F_3(7), F_3(5)+4, F_3(3)+8, F_3(1)+12\} \\
          &\qquad\quad(2.1)\qquad(2.2)\qquad(2.3)\qquad(2.4)\\
\end{aligned}\\
\begin{aligned}
(3)\quad F_4(5)&=max\{4x_4+F_3(5-2x_4)\;|\;x_4\in \{0,1,2\}\}  \\
          &=max\{F_3(5), F_3(3)+4, F_3(1)+8\} \\
          &\qquad\quad(3.1)\qquad(3.2)\qquad(3.3)\\
\end{aligned}\\
\begin{aligned}
(4)\quad F_4(3)&=max\{4x_4+F_3(3-2x_4)\;|\;x_4\in \{0,1\}\}  \\
          &=max\{F_3(3), F_3(1)+4\} \\
          &\qquad\quad(4.1)\qquad(4.2)\\
\end{aligned}\\
\begin{aligned}
(5)\quad F_4(1)&=max\{4x_4+F_3(1-2x_4)\;|\;x_4\in \{0\}\}  \\
          &=max\{F_3(1)\} \\
          &\qquad\quad(5.1)\\
\end{aligned}
\\
-----------------------
\\
\begin{aligned}
(1.1)\quad F_3(9)&=max\{10x_3+F_2(9-5x_3)\;|\;x_3\in \{0,1\}\}  \\
          &=max\{F_2(9), F_2(4)+10\} \\
          &\qquad\quad(1.1.1)\quad(1.1.2)\\
\end{aligned}\\
\begin{aligned}
(1.2)\quad F_3(7)&=max\{10x_3+F_2(7-5x_3)\;|\;x_3\in \{0,1\}\}  \\
          &=max\{F_2(7), F_2(2)+10\} \\
          &\qquad\quad(1.2.1)\quad(1.2.2)\\
\end{aligned}\\
\begin{aligned}
(1.3)\quad F_3(5)&=max\{10x_3+F_2(5-5x_3)\;|\;x_3\in \{0,1\}\}  \\
          &=max\{F_2(5), F_2(0)+10\} \\
          &\qquad\quad(1.3.1)\quad(1.3.2)\\
\end{aligned}\\
\begin{aligned}
(1.4)\quad F_3(3)&=max\{10x_3+F_2(3-5x_3)\;|\;x_3\in \{0\}\}  \\
          &=max\{F_2(3)\} \\
          &\qquad\quad(1.4.1)\\
\end{aligned}\\
\begin{aligned}
(1.5)\quad F_3(1)&=max\{10x_3+F_2(1-5x_3)\;|\;x_3\in \{0\}\}  \\
          &=max\{F_2(1)\} \\
          &\qquad\quad(1.5.1)\\
\end{aligned}
\\
(1.2) \Leftrightarrow (2.1)\\
(1.3) \Leftrightarrow (3.1) \Leftrightarrow (2.2)\\
(1.4) \Leftrightarrow (4.1) \Leftrightarrow (3.2) \Leftrightarrow (2.3)\\
(1.5) \Leftrightarrow (5.1) \Leftrightarrow (4.2) \Leftrightarrow (3.3) \Leftrightarrow (2.4)
\\
-----------------------
\\
\begin{aligned}
(1.1.1)\quad F_2(9)&=max\{7x_2+F_1(9-4x_2)\;|\;x_2\in \{0,1,2\}\}  \\
          &=max\{F_1(9), F_1(5)+7, F_1(1)+14\} \\
\end{aligned}\\
\begin{aligned}
(1.1.2)\quad F_2(4)&=max\{7x_2+F_1(4-4x_2)\;|\;x_2\in \{0,1\}\}  \\
          &=max\{F_1(4), F_1(0)+7\} \\
\end{aligned}\\
\begin{aligned}
(1.2.1)\quad F_2(7)&=max\{7x_2+F_1(7-4x_2)\;|\;x_2\in \{0,1\}\}  \\
          &=max\{F_1(7), F_1(3)+7\} \\
\end{aligned}\\
\begin{aligned}
(1.2.2)\quad F_2(2)&=max\{7x_2+F_1(2-4x_2)\;|\;x_2\in \{0\}\} = max\{F_1(2)\} \\
\end{aligned}\\
\begin{aligned}
(1.3.1)\quad F_2(5)&=max\{7x_2+F_1(5-4x_2)\;|\;x_2\in \{0,1\}\} \\
                   &= max\{F_1(5), F_1(1)+7\} \\
\end{aligned}\\
\begin{aligned}
(1.3.2)\quad F_2(0)&=max\{7x_2+F_1(0-4x_2)\;|\;x_2\in \{0\}\} = max\{F_1(0)\} \\
\end{aligned}\\
\begin{aligned}
(1.4.1)\quad F_2(3)&=max\{7x_2+F_1(3-4x_2)\;|\;x_2\in \{0\}\} = max\{F_1(3)\} \\
\end{aligned}\\
\begin{aligned}
(1.5.1)\quad F_2(1)&=max\{7x_2+F_1(1-4x_2)\;|\;x_2\in \{0\}\} = max\{F_1(1)\} \\
\end{aligned}\\
\\
-----------------------
\\
\begin{aligned}
&F_1(0) = c1*\lfloor\frac{y}{a_1}\rfloor = 6*\lfloor\frac{0}{3}\rfloor = 0\\
\dots \\
&F_1(3) = 6*\lfloor\frac{3}{3}\rfloor = 6\\
\dots \\
&F_1(6) = 6*\lfloor\frac{6}{3}\rfloor = 12\\
\dots \\
&F_1(9) = 6*\lfloor\frac{9}{3}\rfloor = 18\\
\end{aligned}
$$

<br>
Now we can start going back through the recursive calls until, finding maximum values for each step. Looking for when the maximum values are hit, because that will tell us what element should be included in the maximum solution.
<br>

$$
\begin{aligned}
(1.1.1)\quad F_2(9)&=max\{F_1(9), F_1(5)+7, F_1(1)+14\} \\
                   &=max\{18, 6+7, 0+14\} = 18\\
\end{aligned}\\
\begin{aligned}
(1.1.2)\quad F_2(4)&=max\{F_1(4), F_1(0)+7\} \\
                   &=max\{6, 0+7\} = 7\\
\end{aligned}\\
\begin{aligned}
(1.2.1)\quad F_2(7)&=max\{F_1(7), F_1(3)+7\} \\
                   &=max\{12, 6+7\} = 13 \\
\end{aligned}\\
\begin{aligned}
(1.2.2)\quad F_2(2)&=max\{F_1(2)\} = F_1(2) = 0 \\
\end{aligned}\\
\begin{aligned}
(1.3.1)\quad F_2(5)&=max\{F_1(5), F_1(1)+7\} \\
                   &=max\{6, 7\} = 7 \\
\end{aligned}\\
\begin{aligned}
(1.3.2)\quad F_2(0)&=max\{F_1(0)\} = F_1(0) = 0 \\
\end{aligned}\\
\begin{aligned}
(1.4.1)\quad F_2(3)&=max\{F_1(3)\} = F_1(3) = 6 \\
\end{aligned}\\
\begin{aligned}
(1.5.1)\quad F_2(1)&=max\{F_1(1)\} = F_1(1) = 0 \\
\end{aligned}\\
\\
-----------------------
\\
\begin{aligned}
(1.1)\quad F_3(9)&=max\{F_2(9), F_2(4)+10\} \\
                 &=max\{18, 7+10\} = 18 \\
\end{aligned}\\
\begin{aligned}
(1.2)\quad F_3(7)&=max\{F_2(7), F_2(2)+10\} \\
                 &=max\{13, 0+10\} = 13\\
\end{aligned}\\
\begin{aligned}
(1.3)\quad F_3(5)&=max\{F_2(5), F_2(0)+10\} \\
                 &=max\{7, 0+10\} = 10 \\
\end{aligned}\\
\begin{aligned}
(1.4)\quad F_3(3)&=max\{F_2(3)\} = F_2(3) = 6 \\
\end{aligned}\\
\begin{aligned}
(1.5)\quad F_3(1)&=max\{F_2(1)\} = F_2(1) = 0\\
\end{aligned}
\\
-----------------------
\\
\begin{aligned}
(1)\quad F_4(9)&=max\{F_3(9), F_3(7)+4, F_3(5)+8, F_3(3)+12, F_3(1)+16\} \\
               &=max\{18, 13+4, 10+8, 6+12, 0+16\} = 18 \\
\end{aligned}\\
\begin{aligned}
(2)\quad F_4(7)&=max\{F_3(7), F_3(5)+4, F_3(3)+8, F_3(1)+12\} \\
               &=max\{13, 10+4, 6+8, 0+12\} = 14 \\
\end{aligned}\\
\begin{aligned}
(3)\quad F_4(5)&=max\{F_3(5), F_3(3)+4, F_3(1)+8\} \\
               &=max\{10, 6+4, 0+8\} = 10 \\
\end{aligned}\\
\begin{aligned}
(4)\quad F_4(3)&=max\{F_3(3), F_3(1)+4\} \\
               &=max\{6, 0+4\} = 6 \\
\end{aligned}\\
\begin{aligned}
(5)\quad F_4(1)&=max\{F_3(1)\} = F_3(1) = 0\\
\end{aligned}
\\
-----------------------
\\
\text{Finally:}
\begin{aligned}
F_5(9)&=max\{4x_4+F_3(9-2x_4)\;|\;x_4\in \{0,1,2,3,4\}\}  \\
      &=max\{F_4(9), F_4(7)+5, F_4(5)+10, F_4(3)+15, F_4(1)+20\}\\
      &=max\{18, 14+5, 10+10, 6+15, 0+20\}\\
      &=max\{18, 19, 20, 21, 20\}\\
      &=21
\end{aligned}
$$

<br>
Maximum value reached is in $F_5(9) = 21$ and has been reached for $x_5 = 3$ from $F_4(3)$, which gets its maximum value in $x_4 = 0$ from $F_3(3)$, which gets its maximum value in $x_3 = 0$ from $F_2(3)$, which gets its maximum value in $x_2 = 0$ from $F_1(3)$, which gets its maximum value in $x_1 = 1.$
<br>
$
\begin{aligned}
F_5(9)&=max\{F_4(9), F_4(7)+5, F_4(5)+10, F_4(3)+15, F_4(1)+20\}\\
      &=max\{18, 19, 20, 21, 20\}\\
      &=21
\end{aligned}
\rightarrow
\begin{aligned}
F_4(3)&=max\{F_3(3), F_3(1)+4\} \\
      &=max\{6, 0+4\} = 6 \\
\end{aligned}\\
\rightarrow
\begin{aligned}
F_3(3)&=max\{F_2(3)\} = F_2(3) = 6
\end{aligned}
\rightarrow
\begin{aligned}
F_2(3)&=max\{F_1(3)\} = F_1(3) = 6
\end{aligned}
\rightarrow
\begin{aligned}
F_1(3) = 6 \\
\end{aligned}
\\
$
<br>
Maximum solution: $F_{max}=21,\;x=(1,0,0,0,3)$

### Example 2
\begin{equation}
max\;10x_1+40x_2+30x_3+50x_4\\
5x_1+4x_2+6x_3+3x_4\le11\\
x\in Z
\end{equation}

##### Forward solution
First we determine the capacities: $c_1=10, c_2=40,c_3=30,c_4=50,a_1=5,a_2=4,a_3=6,a_4=3$  
Now we can form our tables $F_k(y)$ and $i_k(y)$ using the formulas from above to find $F_{max}$ and our optimum strategy for $x=(0,0,0,0)$:
<table>
<tr><td>

| k\y | 0 | 1 | 2 |  3 |  4 |  5 |  6  |  7  |  8  |  9  |  10 |  11 |
|:---:|:-:|:-:|:-:|:--:|:--:|:--:|:---:|:---:|:---:|:---:|:---:|:---:|
|  1  | 0 | 0 | 0 |  0 |  0 | 10 |  10 |  10 |  10 |  10 |  20 |  20 |
|  2  | 0 | 0 | 0 |  0 | 40 | 40 |  40 |  40 |  80 |  80 |  80 |  80 |
|  3  | 0 | 0 | 0 |  0 | 40 | 40 |  40 |  40 |  80 |  80 |  80 |  80 |
|  4  | 0 | 0 | 0 | 50 | 50 | 50 | 100 | 100 | 100 | 150 | 150 | 150 |

</td>
<td>&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;</td>
<td>

| i\y | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|:---:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:--:|:--:|
|  1  | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |  1 |  1 |
|  2  | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |  2 |  2 |
|  3  | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |  2 |  2 |
|  4  | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |  4 |  4 |

</td></tr> </table>
Finally, we can see that the maximum is reached for $F_4(9)=150 \rightarrow F_{max}=150$<br>
Now we need to form the maximum packing strategy.<br>
We look in the $i$ table to see what item (index) corresponds to the maximum in $F_4(9)$<br> 
$i_4(9)=4$ we add $1$ to the corresponding position in our $x=(0,0,0,0) \rightarrow x=(0,0,0,1)$ <br>
<ol>
<li> $i_4(9-a_4)=i_4(9-3)=i_4(6)=4$, we add $1$ to the corresponding position in our $x=(0,0,0,1) \rightarrow x=(0,0,0,2)$ </li><br>
<li> $i_4(6-a_4)=i_4(6-3)=i_4(3)=4$, we add $1$ to the corresponding position in our $x=(0,0,0,2) \rightarrow x=(0,0,0,3)$ </li><br>
<li> $i_4(3-a_4)=i_4(3-3)=i_4(0)=0 \rightarrow$ we finished filling the solution.</li><br>
</ol>
Maximum solution: $F_{max}=150,\;x=(0,0,0,3)$

##### Backward solution
We form the general formula formula for the maximum possible set:
<br>

$$
\begin{aligned}
F_4(11)&=max\{50x_4+F_3(11-3x_3)\;|\;x_4\in \{0,1,2,3\}\}  \\
       &=max\{F_3(11), F_3(8)+50, F_3(5)+100, F_3(2)+150\}\\
       &\qquad\qquad(1)\qquad\quad(2)\qquad\quad(3)\qquad\qquad(4)
\end{aligned}
\\
-----------------------
\\
\begin{aligned}
(1)\quad F_3(11)&=max\{30x_3+F_2(11-6x_3)\;|\;x_3\in \{0,1\}\}  \\
          &=max\{F_2(11), F_2(5)+30\} \\
          &\qquad\quad(1.1)\qquad(1.2)\\
\end{aligned}\\
\begin{aligned}
(2)\quad F_3(8)&=max\{30x_3+F_2(8-6x_3)\;|\;x_3\in \{0,1\}\}  \\
          &=max\{F_2(8), F_2(2)+30\} \\
          &\qquad\quad(2.1)\qquad(2.2)\\
\end{aligned}\\
\begin{aligned}
(3)\quad F_3(5)&=max\{30x_3+F_2(5-6x_3)\;|\;x_3\in \{0\}\}  \\
          &=max\{F_2(5)\} \\
          &\qquad\quad(3.1)\\
\end{aligned}\\
\begin{aligned}
(4)\quad F_3(2)&=max\{30x_3+F_2(2-6x_3)\;|\;x_3\in \{0\}\}  \\
          &=max\{F_2(2)\}\\
          &\qquad\quad(3.1)\\
\end{aligned}
\\
-----------------------
\\
\begin{aligned}
(1.1)\quad 
F_2(11)&=max\{40x_2+F_1(11-4x_2)\;|\;x_2\in \{0,1,2\}\}  \\
       &=max\{F_1(11), F_1(7)+40, F_1(3)+80\} \\
\end{aligned}
\\
\begin{aligned}
(1.2)\quad 
F_2(5)&=max\{40x_2+F_1(5-4x_2)\;|\;x_2\in \{0,1\}\}  \\
       &=max\{F_1(5), F_1(1)+40\} \\
\end{aligned}
\\
\begin{aligned}
(2.1)\quad 
F_2(8)&=max\{40x_2+F_1(8-4x_2)\;|\;x_2\in \{0,1,2\}\}  \\
       &=max\{F_1(8), F_1(4)+40, F_1(0)+80\} \\
\end{aligned}
\\
\begin{aligned}
(2.2)\quad 
F_2(2)&=max\{40x_2+F_1(2-4x_2)\;|\;x_2\in \{0\}\}  \\
       &=max\{F_1(2)\} \\
\end{aligned}
\\
\begin{aligned}
(3.1)\quad 
F_2(5)&=max\{40x_2+F_1(5-4x_2)\;|\;x_2\in \{0,1\}\}  \\
       &=max\{F_1(5), F_1(1)+40\} \\
\end{aligned}
\\
\begin{aligned}
(4.1)\quad 
F_2(2)&=max\{40x_2+F_1(2-4x_2)\;|\;x_2\in \{0\}\}  \\
       &=max\{F_1(2)\} \\
\end{aligned}
\\
-----------------------
\\
\begin{aligned}
&F_1(0) = c1*\lfloor\frac{y}{a_1}\rfloor = 10*\lfloor\frac{0}{5}\rfloor = 0\\
\dots \\
&F_1(5) = 10*\lfloor\frac{5}{5}\rfloor = 10\\
\dots \\
&F_1(10) = 10*\lfloor\frac{10}{5}\rfloor = 20\\
&F_1(11) = 20\\
\end{aligned}
$$

<br>
Now we can start going back through the recursive calls until, finding maximum values for each step. Looking for when the maximum values are hit, because that will tell us what element should be included in the maximum solution.
<br>

$$
\begin{aligned}
(1.1)\quad 
F_2(11)&=max\{F_1(11), F_1(7)+40, F_1(3)+80\} \\
       &=max\{20, 10+40, 0+80\} = 80\\
\end{aligned}
\\
\begin{aligned}
(1.2)\quad 
F_2(5)&=max\{F_1(5), F_1(1)+40\} \\
      &=max\{10, 40\} = 40\\
\end{aligned}
\\
\begin{aligned}
(2.1)\quad 
F_2(8)&=max\{F_1(8), F_1(4)+40, F_1(0)+80\} \\
       &=max\{10, 0+40, 0+80\} = 80 \\
\end{aligned}
\\
\begin{aligned}
(2.2)\quad 
F_2(2)&=max\{F_1(2)\} = F_1(2) = 0 \\
\end{aligned}
\\
\begin{aligned}
(3.1)\quad 
F_2(5)&= 40\; \text{(calculated above)} \\
\end{aligned}
\\
\begin{aligned}
(4.1)\quad 
F_2(2)&= 0\; \text{(calculated above)}\\
\end{aligned}
\\
\\
-----------------------
\\
\begin{aligned}
(1)\quad F_3(11)&=max\{F_2(11), F_2(5)+30\}   \\
          &=max\{80, 40+30\} = 80 \\
\end{aligned}\\
\begin{aligned}
(2)\quad F_3(8)&=max\{F_2(8), F_2(2)+30\} \\
          &=max\{80, 0+30\} = 80 \\
\end{aligned}\\
\begin{aligned}
(3)\quad F_3(5)&=max\{F_2(5)\} = F_2(5) = 40\\
\end{aligned}\\
\begin{aligned}
(4)\quad F_3(2)&=max\{F_2(2)\} = F_2(2) = 0 \\
\end{aligned}
\\
\\
-----------------------
\\
\text{Finally:}
\begin{aligned}
F_4(11)&=max\{50x_4+F_3(11-3x_3)\;|\;x_4\in \{0,1,2,3\}\}  \\
       &=max\{F_3(11), F_3(8)+50, F_3(5)+100, F_3(2)+150\}\\
       &=max\{80, 80+50, 40+100, 0+150\}\\
       &=max\{80, 130, 140, 150\}\\
       &=150\\
\end{aligned}
\\
$$
<br>
Maximum value reached is in $F_4(11) = 150$ and has been reached for $x_4 = 3$ from $F_3(2)$, which gets its maximum value in $x_3 = 0$ from $F_2(2)$, which gets its maximum value in $x_2 = 0$ from $F_1(2)$, which gets its maximum value in $x_3 = 0$ from $F_1(2)$.<br>
$
\begin{aligned}
F_4(11)&=max\{F_3(11), F_3(8)+50, F_3(5)+100, F_3(2)+150\}\\
       &=max\{80, 130, 140, 150\} = 150\\
\end{aligned}
\rightarrow
\begin{aligned}
F_3(2)&=max\{F_2(2)\} = 0 \\
\end{aligned}
\rightarrow
\begin{aligned}
F_2(2)&=max\{F_1(2)\} = 0 \\
\end{aligned}
\rightarrow
\begin{aligned}
F_1(2) = 0 \\
\end{aligned}
\\
$
<br>
Maximum solution: $F_{max}=150,\;x=(0,0,0,3)$

c82ec95fcdd63499c71a318dd2f5a314ee056e47
ipynb
Jupyter Notebook
07. Knapsack problem/Seminarski.ipynb
lkora/DS3
653115657d8c42f501dcb5dbf25c892a4e0ed3d1
MIT
2020-04-19T12:17:02.000Z
2020-04-19T12:17:02.000Z
07. Knapsack problem/Seminarski.ipynb
lkora/MATF-DS3
653115657d8c42f501dcb5dbf25c892a4e0ed3d1
MIT
07. Knapsack problem/Seminarski.ipynb
lkora/MATF-DS3
653115657d8c42f501dcb5dbf25c892a4e0ed3d1
MIT
Qwen/Qwen-72B
1. YES
2. YES