Application of the Knapsack Algorithm

Question

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??

$$$$

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?? How can we find which elements we have to take??

EDIT1:

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$ ??

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

EDIT2:

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

   Algorithm 01Knapsack(S, W):

    Input: set S of n items with benefit bi
    and weight wi
    ; maximum weight W

    Output: benefit of best subset of S with
    weight at most W

    let A and B be arrays of length W + 1
    for w ← 0 to W do
          B[w] ← 0
    for k ← 1 to n do
          copy array B into array A
          for w ← wk to W do
              if A[w−wk] + bk > A[w] then
                   B[w] ← A[w−wk] + bk
    return B[W] 

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

$$B:\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$

$k \leftarrow 1 \\ A:\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$ $$\\ w \leftarrow 2 : \\ A[w-w_1]+b_1>A[w] \\ A[2-2]+b_1 >A[2] \\ A[0]+b_1>A[2] \\ 0+3>0 \checkmark \\ B[2] \leftarrow A[w-w_1]+b_1=3 \\--------------------- \\ w \leftarrow 3 : \\ A[w-w_1]+b_1>A[w] \\ A[3-2]+b_1 >A[3] \\ A[1]+b_1>A[3] \\ 0+3>0 \checkmark \\ B[3] \leftarrow A[w-w_1]+b_1=3 \\ ---------------------\\ w \leftarrow 4 : \\ A[w-w_1]+b_1>A[w] \\ A[4-2]+b_1 >A[4] \\ A[2]+b_1>A[4] \\ 0+3>0 \checkmark \\ B[4] \leftarrow A[w-w_1]+b_1=3 \\ ---------------------\\ w \leftarrow 5 : \\ A[w-w_1]+b_1>A[w] \\ A[5-2]+b_1 >A[5] \\ A[3]+b_1>A[5] \\ 0+3>0 \checkmark \\ B[5] \leftarrow A[w-w_1]+b_1=3$$

$$B:\begin{bmatrix} 0 & 0 & 3 & 3 & 3 & 3 \end{bmatrix}$$

$k \leftarrow 2 \\ A:\begin{bmatrix} 0 & 0 & 3 & 3 & 3 & 3 \end{bmatrix}$ $$\\ w \leftarrow 3 : \\ A[w-w_2]+b_2>A[w] \\ A[3-3]+b_2 >A[3] \\ A[0]+b_2>A[3] \\ 0+4>3 \checkmark \\ B[3] \leftarrow A[w-w_2]+b_2=4 \\--------------------- \\ w \leftarrow 4 : \\ A[w-w_2]+b_2>A[w] \\ A[4-3]+b_2 >A[4] \\ A[1]+b_2>A[4] \\ 0+4>3 \checkmark \\ B[4] \leftarrow A[w-w_2]+b_2=4 \\ ---------------------\\ w \leftarrow 5 : \\ A[w-w_2]+b_2>A[w] \\ A[5-3]+b_2 >A[5] \\ A[2]+b_2>A[5] \\ 3+4>3 \checkmark \\ B[5] \leftarrow A[w-w_2]+b_2=7$$

$$B:\begin{bmatrix} 0 & 0 & 3 & 4 & 4 & 7 \end{bmatrix}$$

$k \leftarrow 3 \\ A:\begin{bmatrix} 0 & 0 & 3 & 4 & 4 & 7 \end{bmatrix}$ $$\\ w \leftarrow 4 : \\ A[w-w_3]+b_3>A[w] \\ A[4-4]+b_3 >A[4] \\ A[0]+b_3>A[4] \\ 0+5>4 \checkmark \\ B[4] \leftarrow A[w-w_3]+b_3=5 \\--------------------- \\ w \leftarrow 5 : \\ A[w-w_3]+b_3>A[w] \\ A[5-4]+b_3 >A[5] \\ A[1]+b_3>A[5] \\ 0+5>7 \times$$

$$B:\begin{bmatrix} 0 & 0 & 3 & 4 & 5 & 7 \end{bmatrix}$$

$k \leftarrow 4 \\ A:\begin{bmatrix} 0 & 0 & 3 & 4 & 5 & 7 \end{bmatrix}$ $$\\ w \leftarrow 5 : \\ A[w-w_4]+b_4>A[w] \\ A[5-5]+b_4 >A[5] \\ A[0]+b_4>A[5] \\ 0+6>7 \times$$

So, $B[5]=7$, that means that the optimal choice has maximal benefit $7$.

Can we deduce from the algorithm which items we have to choose??

$$$$

EDIT3:

I found that for the algorithm :

K(0,j)=0, for all j=0,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)

to find which items we should take there is the following algorithm:

  j=n, k=W
    while i,k > 0
        if K[k,j] ≠ K[k,j-1] then
            mark the j-th item as in the knapsack
            j = j−1, k = k-w_j
       else
            j = j−1

Is this correct?? Or should it be

j=n, k=W
        while i,k > 0
            if K[k,j] ≠ K[k,j-1] then
                mark the j-th item as in the knapsack
                k = k-w_j, j = j−1 // shouldn't we first reduce the weight and then go to the previous item?? 
           else
                j = j−1

Answer 1

The first algorithm is correct, and you have interpreted it the right way.

Added: It looks like the first algorithm allows you to choose the same item more than once (but must be an integer). Consider $K(4)=6$, this means if the knapsack can afford a weight of $4$, the max value will be $6$. This can only be satisfied if you pick $2 \times$ (item $1$). However, for the second and fourth algorithm, you can only pick $0$ or $1$ unit of each item (hence those algorithms are called $0$-$1$ knapsack algorithm).

For the second algorithm, I think there is a slight error. It should be

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  // The error is here. Use >= instead of >
             K(w,j)=max{K(w,j-1),K(w-w_j,j-1)+v_j} 
         else 
             K(w,j)=K(w,j-1) 

You should be able to find that $K(2,5) = 7$, and then $K(3,5) = 7$ and $K(4,5) = 7$. This result means the maximum value you can carry in the knapsack is $7$, but it does not tell which items you should put into the knapsack. By inspection of values, the only possibility is the first two items.

For the third algorithm (fractional knapsack problem), it is correct, but you should interpret the result as to bring weight $2$ of item $1$ and weight $3$ of item $2$. It happens in your example that item $1$ is of weight $2$ and item $2$ is of weight $3$. So this means you should bring the whole item $1$ and whole item $2$.

You may consider if the knapsack can only support $4$ units of weight instead of $5$. Then by running this algorithm, you will have $x_1 = 2$, $x_2 = 2$. This means you should bring weight $2$ of item $1$ and weight $2$ of item $2$. In such case, you should bring $\frac{2}{3}$ of item $2$. That is why this is known as fractional knapsack problem, and is only applicable on items that can be cut into portions.

Edit: The OP has added a fourth algorithm (in Edit 2 part of the post). The algorithm is correct, but the algorithm itself does not tell which items should be put in the knapsack; it only returns the maximum value (or benefit) that the knapsack can carry. We still need to inspect by ourselves and find the list of items which benefits sum to the return value. And sometimes there may be more than one answer. e.g. Consider the case if item $4$ has weight $5$ and benefit $7$ instead of $6$, then there will be two possible solutions.