MHB Solving Knapsack Problem: 1st & 2nd Algorithm

[mathmari]

Hey!

I want to apply the Knapsack algorithm at the following:

n = 4 (# of elements)
W = 5 (max weight)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)

The first version of the algorithm is the following:

K(0)=0
for w=1 to W
    K(w)=max_{w_i \leq w} {K(w-w_i)+v_i}

I have found the following:

$$K(1)=\max_{w_i \leq 1} \{K(1-w_i)+v_i\}=0 \\ K(2)=\max_{w_i \leq 2} \{K(2-w_i)+v_i\}=K(2-2)+3=K(0)+3=3 \\ K(3)=\max_{w_i \leq 3} \{K(3-w_i)+v_i \}=\max \{K(3-3)+4, K(3-2)+3\}=\max \{K(0)+4, K(1)+3\}=\max \{4, 3\}=4 \\ K(4)=\max_{w_i \leq 4} \{K(4-w_i)+v_i\}=\max \{K(4-4)+5, K(4-3)+4, K(4-2)+3\}=\max \{K(0)+5, K(1)+4, K(2)+3\}=\max \{5, 4, 6\}=6 \\ K(5)=\max_{w_i \leq 5} \{K(5-w_i)+v_i\}=\max \{K(5-5)+6, K(5-4)+5, K(5-3)+4, K(5-2)+3\}=\max \{K(0)+6, K(1)+5, K(2)+4, K(3)+3\}=\max \{6, 5, 7, 7\}=7$$

At $K(5)=7$, the $7$ came from the elements $(2,3)$ and $(3,4)$. So, the optimal choice is to take these two elements with benefit $3+4=7$. Is this correct?? (Wondering)
The second version of the Knapsack algorithm is the following:

K(0,j)=0, for all j=1,2, ... ,n 
K(w,0)=0, for all w=1,2, ... ,W 
for j<-1 to n 
     for w<-1 to W 
          if w>w_j 
             K(w,j)=max{K(w,j-1),K(w-w_j,j-1)+v_j} 
          else 
             K(w,j)=K(w,j-1)

I have found the following:

$$K(1,1)=K(1,0)=0 \\ K(2, 1)=K(2, 0)=0 \\ K(3, 1)=\max \{K(3, 0), K(3-2, 0)+3\}=\max \{0, 0+3\}=\max \{0, 3\}=3 \\ K(4, 1)=\max \{K(4, 0), K(4-2, 0)+3\}=\max \{0, 0+3\}=\max \{0, 3\}=3 \\ K(5, 1)=\max \{K(5, 0)+K(5-2, 0)+3\}=\max \{0, 0+3\}=\max \{0, 3\}=3 \\ \\
K(1, 2)=K(1, 1)=0 \\ K(2, 2)=K(2, 1)=0 \\ K(3, 2)=K(3, 1)=3 \\ K(4, 2)=\max \{K(4, 1), K(4-3, 1)+4\}=\max \{3, 0+4\}=\max \{3, 4\}=4 \\ K(5, 2)=\max \{K(5, 1), K(5-3, 1)+4\}=\max \{3, 0+4\}=\max \{3, 4\}=4 \\ \\
K(1, 3)=K(1, 2)=0 \\ K(2, 3)=K(2, 2)=0 \\ K(3, 3)=K(3, 2)=3 \\ K(4, 3)=K(4, 2)=4 \\ K(5, 3)=\max \{K(5, 2), K(5-4, 2)+5\}=\max \{4, 0+5\}=\max \{4, 5\}=5 \\ \\
K(1, 4)=K(1, 3)=0 \\ K(2, 4)=K(2, 3)=0 \\ K(3, 4)=K(3, 3)=3 \\ K(4, 4)=K(4, 3)=4 \\ K(5, 4)=K(5, 3)=5$$ Is this correct?? (Wondering) How can we find which elements we have to take?? (Wondering)

 

[mathmari]

I found the following algorithm for the fractional version of the Knapsack problem:

    Algorithm fractionalKnapsack(S, W) 

    Input: set S of items w/ benefit bi
    and weight wi
    ; max. weight W

    Output: amount xi of each item i
    to maximize benefit with
    weight at most W

    for each item i in S
         xi ← 0
         vi ← bi / wi {value}
    w ← 0 {total weight}
    while w < W
         remove item i with highest vi
         xi ← min{wi , W − w}
         w ← w + min{wi , W − w}

I tried to apply this algorithm and I got the following:

$$x_1 \leftarrow 0 \\ v_1 \leftarrow \frac{3}{2}=1.5 \\ x_2 \leftarrow 0 \\ v_2 \leftarrow \frac{4}{3}=1.33 \\ x_3 \leftarrow 0 \\ v_3 \leftarrow \frac{5}{4}=1.25 \\ x_4 \leftarrow 0 \\ v_4 \leftarrow \frac{6}{5}=1.2 \\ w \leftarrow 0 \\ 0<5 \checkmark \\ \ \ \ \ \ \text{ remove item } =1, \max v_i=1.5 \\ \ \ \ \ \ x_1 \leftarrow \min \{w_1, W-w\}=\min \{2, 5-0\}=\min \{2, 5\}=2 \\ \ \ \ \ \ w \leftarrow 2+\min \{w_1, W-w\}=0+2=2 \\ 2<5 \checkmark \\ \ \ \ \ \ \text{ remove item } i=2, \max v_i=1.33 \\ \ \ \ \ \ x_2 \leftarrow \min \{w_2 , W-w\}=\min \{3, 5-2\}=\min \{3, 3\}=3 \\ \ \ \ \ \ w \leftarrow w+\min \{w_2, W-w\}=2+3=5 \\ 5<5 \times$$ Does this mean that the optimal choice is to take two times the item $1$ and three times the item $2$ ?? (Wondering)

But isn't then the total weight greater than $5$ ?? (Wondering)