Question

Design a local search algorithm for the 0-1 knapsack problem. Assume there are n items x1 ... xn each with weight wi and value vi. The knapsack can have at most one of each item and the total weight cannot exceed W. You want to maximize the total value in the knapsack.

Question 1: (7 points) Show the psuedocode/explanation for your algorithm.
Question 2. (3 points) Is it guaranteed to find an optimal solution? Justify your answer.

Answer 1

// v CONTAINS THE VALUES OF THE ITEMS 

// w CONTAINS THE WEIGHT OF THE ITEMS 

// n NUMBER OF ITEMS /

/ W TOTAL WEIGHT CAPACITY 

// r stores the result 

DP_0-1_knapsack (v, w, n, W) 

for w from 0 to W do 

r[0, w] = 0 

end for 

for j from 1 to n do 

for k from 0 to W do 

if k >= w[j] then 

r[j, k] = max(r[j-1, k-w[j]] + v[j], r[j-1, k] ) 

else 

r[j, k] = r[j-1, k] 

The above-given pseudocode is the pseudocode for the dynamic programming (DP) based solution of the 0-1 knapsack problem. In the DP-based approach, a 2D array of sizes (n+1) and (W+1) is created and is filled for each n and W value. The result of the previous computation is used in the next computation. This ultimately leads to the final cell of our 2D array which will be the required solution for our problem.

The dynamic programming-based solution is guaranteed to find the optimal solution. This is not the case with the Greedy approach which is used to solve the fractional knapsack problem. The greedy approach cannot be used to solve the 0-1 knapsack problem because it doesn't always guarantee optimality in the case of a 0-1 knapsack.

Example:

Suppose we have 3 items A, B, and C, and a knapsack with a weight capacity of W=4.

The weight and values for the items are given below,

w=[3, 2, 2]

v=[1.8 , 1 , 1]

If the greedy approach is used then it will select the first element A and terminate the program with a value of 1.8 as no more space is left in a knapsack to accommodate more items. Whereas the most optimal solution will be the itmes B and C in the Knapsack as they will lead to a total value of 2 in the knapsack. The dynamic programming is able to get this optimal solution whereas the greedy-based solution fails.