FOR FREE YEAR SOLVED

Overview:

The knapsack problem is a combinatorial optimization problem. The word knapsack in English means a bag carried on the back. In 0/1 knapsack problem the knapsack has a certain limited capacity let us say ‘w_max’. Now we want to pack ‘n’ items in the knapsack in such a manner that:-

l Each item i has a value v_i and a weight w_i.

l We can carry as many items we want to but the total weight of the items taken must not exceed w_max.

l A fractional amount of item cannot be taken.

Let us try to understand what 0/1 knapsack problem is using an interesting elementary example. Let us suppose ,a robber breaks into a electronic supermarket at night when no one is around. In the supermarket there are ‘n’ number of unique smart phones, and each of the smart phones has a weight ‘w_i’ and market value ‘v_i’. The robber was carrying a small knapsack in order to not look suspicious to anyone, thus he cannot carry more weight than a certain limit ‘w_max’. The problem to be solved here is which smart phones the robber should take away with him to get the highest value? In this case the robber cannot take a fraction of a smart phone, he has to either take it or he has to leave it behind, thus making it a 0/1 knapsack problem.

Procedure to solve 0/1 Knapsack problem using Dynamic Programming with an example:

Since greedy approach doesn’t ensure optimal solution, thus the solution cannot be obtained using greedy approach. Thus we use Dynamic Programming Approach.

Let us assume, we have a knapsack which has a maximum weight capacity of 5.

w_max = 5

Now total number of items present is 4.

n = 4

The market value and weight of each item is described as follows :-

Now for solving , we create a table T[i,w] where , i(i.e the row) denotes number of items and w (i.e the column) denotes the weight of the items.

Since we have a total number of n = 4 items, we have 5 rows from Now for solving , we create a table T[i,w] where , i (i.e the row) denotes number of items and w (i.e the column) denotes the weight of the items.

The i^th row is filled with 0, because when 0 items are considered, thus the weight of the knapsack remains 0.

Then we fill the first column with 0, because when weight is 0 then 0 items are considered.

Thus the table T[i][w] looks like this

Rule to fill the rest of the table T[i,w]

a) If wi> w then,

T[i,w] = T[i-1,w]

b) If wi<= w then,

T[i,w] = max( T[i-1,w] , vi + T[i-1,w-wi])

After calculation the table T[i,w] becomes 

Maximum value earned isT[n,Wmax]

Since n = 4 and Wmax = 5, maximum value earned is

T[4,5] = 140

Algorithm:

Input:

1.    Total number of inputs n.

2.    Maximum weight capacity of the knapsack w_max.

3.    Array of size n containing the value of each of the items.

4.    Array of size n containing the weight of each of the items.

Output:

1.    Display the maximum value of the knapsack.

Algo:

Step 1: Start

Step 2: Defining the max function

l  If x > y then return y

l  Else return x

Step 3: Defining the knapsack function

l Create an array with n+1 rows and w_max+1 columns.

l  Fill the 0^th row with 0.

l Fill the 0^th column with 0.

l  Repeat the substeps for i = 0 to n.

Repeat the substeps for j = 0 to w_max.

If w_i< = w_maxthen,

T[i][w]    max(T[i-1][w], value[i] +        T[i-1][w - weight[i]])

Else then,

T[i][w]   T[i-1][w]

l  Display “The maximum value of the knapsack is T[n][W_max]

Step 4: Defining the main function

l knapsack(n,w_max,value,weight)

Step 5: Stop