Here I am going to explain about 0/1 Knapsack problem using dynamic programming. We already know about what is knapsack problem? in greedy approach.

The main concept in both the approach is same that is we must select the item and fill it into sack (just like a bag) in such a way that we get more profit.

In greedy approach we can fill the item into the sack partially that means if the weight of item 20 and the space available in sack is 10 than can select 10 weight out of 20 weight and put into the sack that means factorial part is allowed here.

But in dynamic programming when we solving knapsack problem fractional part is not allowed. We can select either complete portion of item that means 1 or select nothing from the item that means 0 , that's why it is known as 0/1 knapsack problem.

Here the item / object are not divisible or breakable such as mobiles, laptop, mouse, keyboard etc.

So here our objective is to maximise profit:

So above method is time consuming if we are finding all the possibilities for the selection of items.

Now we will discuss how we do same thing in easy way so that we save time and effort. Let we understand dynamic programming by the help of an example.

Example:1

suppose we have

P = { 1, 2, 5, 6 } 

W= { 2, 3, 4, 5 }

and m=8 , n=4

For solving the above method we are using tabulation method.

Create column according to the capacity of sack / bag i.e here 8.

Taking all object at a time is not possible , So here one by one we will consider the object/item like 1, 2, 3, ...,8. 

Here we create table of 9 columns which is depend on the value of m i.e m=8. We have 4 items so we take 5 rows.

Initially R row and C column according to the above table will be 0.

Note: (According to this table)

If we consider row-2 for item-2 than we also consider item 1 with their (P,W).

If we consider row-3 for item-3 than we consider item-2 and item-1 with their (P,W).

If we consider row-4 for item-4 than we consider item-3,item-2 and item-1 with their (P,W).

If we consider row-5 than we consider item-4,item-3,item-2 and item-1 with their (P,W).

So we can say that if we are in ith row than we consider all the previous rows also.

Now Let we start:

If we select item-1 than we see what is the profit i.e 1, So put 1 in col-2 column.

Now understand the logic for putting profit in columns suppose here for item-1 the weight is 2, Now imagine can you put suppose 2 kg of item in 1 kg of bag the answer is no so we put 0(profit) in column 1, 

Now check for next can you put suppose 2 kg of item in 2 kg of bag the answer is yes,so we put 1(profit) in column 2, In the same way answer is yes for all column 3,4,5,6,7,8 so we put 1 in all column.

Now the table will be

Now we talk about right side of column-3. what we put here? So I already told you when we take row-2 than we also consider row-1 with (P,W). Now here we have two choice whether we can select 2 or 3 of weight.

Let we calculate profit 

For row-2 & col-3

step-1 : 2 is profit of weight=3 of item-2

step-2 : Subtract col-3 index i.e 3 to weight of item-2 i.e 3, such as  (3-3=0) then we get 0 so go to col-0 and row-1(i.e go one step up) is 0.

step-3 : The value above (one step up i.e row-1) from row-2 in col-3 is 1

step-4 : adding step-1 + step-2 i.e (2 + 0)=2

step-5 : Find maximum of step-4 and step-3 i.e max(2 , 1)=2

so write 2 col-3 row-2 as we show in above Now next

For row-2 & col-4

step-1 : 2 is profit of weight=3 of item-2

step-2 : Subtract col-4 index i.e 4 to weight of item-2 i.e 3, such as  (4-3=1) then we get 1 so go to col-1 and row-1(i.e go one step up) is 0.

step-3 : The value above (one step up i.e row-1) from row-2 in col-4 is 1

step-4 : Adding step-1 + step-2 i.e (2 + 0)=2

step-5 : Find maximum of step-4 and step-3 i.e max(2 , 1)=2

                                OR

Note: 

For the above process Formula will be:

M[i,W] = max ( m[i-1,W] , ( m[i-1] , W - W[i] )+ P[i] ) )

where : 

                i is items such as (1,2,3,4..)

                w is weight such as (0,1,2,3,4,5,6,7,8)

Let we find For row-2 & col-4 by using formula.

here i=2 w=4

M(2,4) = max (m(1,4), ( m(1, 4-3)+2))

M(2,4)= max (1,(m(1,1)+2))

M(2,4)= max (1,(0+2))

M(2,4)= max (1,2)

M(2,4)= 2

so for item-2 col-4 value is 2

so write 2 col-4 row-2 

For row-2 & col-5

step-1 : 2 is profit of weight=3 of item-2

step-2 : Subtract col-5 index i.e 5 to weight of item-2 i.e 3, such as  (5-3=2) then we get 2 so go to col-2 and row-1(i.e go one step up) is 1.

step-3 : The value above (one step up i.e row-1) from row-2 in col-5 is 1

step-4 : Adding step-1 + step-2 i.e (2 + 1)=3

step-5 : Find maximum of step-4 and step-3 i.e max(3 , 1)=3

                                    or

For the above process Formula will be:

M[i,W] = max ( m[i-1,W] , ( m[i-1] , W - W[i] )+ P[i] ) )

where : 

                i is items such as (1,2,3,4..)

                w is weight such as (0,1,2,3,4,5,6,7,8)

Let we find For row-2 & col-5 by using formula.

here i=2 w=5

M(2,5) = max (m(1,5), ( m(1, 5-3)+2))

M(2,5)= max (1,(m(1,2)+2))

M(2,5)= max (1,(1+2))

M(2,5)= max (1,3)

M(2,5)= 3

so write 3 col-5 row-2

For row-2 & col-6

step-1 : 2 is profit of weight=3 of item-2

step-2 : Subtract col-6 index i.e 6 to weight of item-2 i.e 3, such as  (6-3=3) then we get 2 so go to col-2 and row-1(i.e go one step up) is 1.

step-3 : The value above (one step up i.e row-1) from row-2 in col-6 is 1

step-4 : Adding step-1 + step-2 i.e (2 + 1)=3

step-5 : Find maximum of step-4 and step-3 i.e max(3 , 1)=3

                                      or

For the above process Formula will be:

M[i,W] = max ( m[i-1,W] , ( m[i-1] , W - W[i] )+ P[i] ) )

where : 

                i is items such as (1,2,3,4..)

                w is weight such as (0,1,2,3,4,5,6,7,8)

Let we find For row-2 & col-6 by using formula.

here i=2 w=5

M(2,6) = max (m(1,6), ( m(1, 6-3)+2))

M(2,6)= max (1,(m(1,3)+2))

M(2,6)= max (1,(1+2))

M(2,6)= max (1,3)

M(2,6)= 3

so write 3 col-6 row-2

Same way for col 7 & col 8

Now Calculate for row-3

Here  weight of item is 4 and profit is 5

Write as it is value for col-1,col-2,col-3 of row-3

Now calculate for row-3 & col-4

step-1 : 5 is profit of weight=4 of item-3

step-2 : Subtract col-4 index i.e 4 to weight of item-3 i.e 4, such as  (4-4=0) then we get 0 so go to col-0 and row-2(i.e go one step up)  is 0.

step-3 : The value above (one step up i.e row-2) from row-3 in col-4 is 2

step-4 : Adding step-1 + step-2 i.e (5 + 0)=5

step-5 : Find maximum of step-4 and step-3 i.e max(5 , 2)=5

                                      or

For the above process Formula will be:

M[i,W] = max ( m[i-1,W] , ( m[i-1] , W - W[i] )+ P[i] ) )

where : 

                i is items such as (1,2,3,4..)

                w is weight such as (0,1,2,3,4,5,6,7,8)

Let we find For row-3 & col-4 by using formula.

here i=3 w=4

M(3,4) = max (m(2,4), ( m(2, 4-4)+5))

M(3,4)= max (2,(m(2,0)+5))

M(3,4)= max (1,(0+5))

M(3,4)= max (1,5)

M(3,4)= 5

so write 5 in col-4 row-3

Now calculate for row-3 & col-5

step-1 : 5 is profit of weight=4 of item-3

step-2 : Subtract col-5 index i.e 5 to weight of item-3 i.e 4, such as  (5-4=1) then we get 0 so go to col-0 and row-2(i.e go one step up) is 0.

step-3 : The value above (one step up i.e row-2) from row-3 in col-4 is 2

step-4 : Adding step-1 + step-2 i.e (5 + 0)=5

step-5 : Find maximum of step-4 and step-3 i.e max(5 , 2)=5

                                      or

For the above process Formula will be:

M[i,W] = max ( m[i-1,W] , ( m[i-1] , W - W[i] )+ P[i] ) )

where : 

                i is items such as (1,2,3,4..)

                w is weight such as (0,1,2,3,4,5,6,7,8)

Let we find For row-3 & col-5 by using formula.

here i=3 w=5

M(3,5) = max (m(2,5), ( m(2, 5-4)+5))

M(3,5)= max (3,(m(2,1)+5))

M(3,5)= max (3,(0+5))

M(3,5)= max (3,5)

M(3,5)= 5

Now calculate for row-3 & col-6

Now calculate for row-3 & col-7

step-1 : 5 is profit of weight=4 of item-3

step-2 : Subtract col-7 index i.e 7 to weight of item-3 i.e 4, such as  (7-4=3) then we get 3 so go to col 3 and row-2(i.e go one step up) is 2.

step-3 : The value above (one step up i.e row-2) from row-3 in col-7 is 3

step-4 : Adding step-1 + step-2 i.e (5 + 2)=7

step-5 : Find maximum of step-4 and step-3 i.e max(7 , 3)=7

                                      or

For the above process Formula will be:

M[i,W] = max ( m[i-1,W] , ( m[i-1] , W - W[i] )+ P[i] ) )

where : 

                i is items such as (1,2,3,4..)

                w is weight such as (0,1,2,3,4,5,6,7,8)

Let we find For row-3 & col-7 by using formula.

here i=3 w=7

M(3,7) = max (m(2,7), ( m(2, 7-4)+5))

M(3,7)= max (3,(m(2,3)+5))

M(3,7)= max (3,(2+5))

M(3,7)= max (3,7)

M(3,7)= 7

Now calculate for row-3 & col-8

step-1 : 5 is profit of weight=4 of item-3

step-2 : Subtract col-8 index i.e 8 to weight of item-3 (i.e 4), such as  (8-4=4) then we get 4 so go to col 4 and row-2(i.e go one step up)  is 2.

step-3 : The value above (one step up i.e row-2) from row-3 in col-8 is 3

step-4 : Adding step-1 + step-2 i.e (5 + 2)=7

step-5 : Find maximum of step-4 and step-3 i.e max(7 , 3)=7

                                      or

For the above process Formula will be:

M[i,W] = max ( m[i-1,W] , ( m[i-1] , W - W[i] )+ P[i] ) )

where : 

                i is items such as (1,2,3,4..)

                w is weight such as (0,1,2,3,4,5,6,7,8)

Let we find For row-3 & col-8 by using formula.

here i=3 w=8

M(3,8) = max (m(2,8), ( m(2, 8-4)+5))

M(3,8)= max (3,(m(2,3)+5))

M(3,8)= max (3,(2+5))

M(3,8)= max (3,7)

M(3,8)= 7

Now Calculate for Item-4 or Row-4

Here  weight of item is 5 and profit is 6

Write as it is value for col-1,col-2,col-3,col-4 of row-4

Now calculate for row-4 & col-5

Same procedure is done as above is given

Now calculate for row-4 & col-6

Same procedure is done as above is given

Now calculate for row-4 & col-7

Same procedure is done as above is given

Now calculate for row-4 & col-8

Same procedure is done as above is given

Now how we find considered item in a sack the procedure is first pickup the maximum profit.What we get like here is 8 then we find whether this value is available in previous row. If not available than 8 is final profit.

Example:2

let we understand by some example.

Suppose : W = {3 , 4 , 6 , 5}  and P = {2 , 3 , 1 , 4} 

                where m=8 and n=4.

By apply the above procedure we get final table given below.

Now by the help of above table find maximum profit.

So pick the maximum profit form table i.e 6 which is in row-4. Now we again search or find 6 in above row i.e row-3 , if 6 is available  than again search in above row i.e row-2 but here 6 is not present, So we take 6 in row-3 and find profit of that row-3 i.e for item-3 profit is 4.

Now subtract 6 to profit i.e 6-4=2

Now we find 2 in above row i.e in row-2 & col-3 , if 2 is available ? yes 

So in row-1 & col-3 , 2 is available , 

For row-1 & col-3 item=1 , weight=3 and profit=2

So finally we get profit=2.

Practice Questions:

1. Find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach 

where: 

n = 4

w=5 kg

(w1, w2, w3, w4) = (2, 3, 4, 5)

(p1, p2, p3, p4) = (3, 4, 5, 6)

Answer: Maximum Profit = 7 and Item Selected (1100) i.e p1 & p2 Selected

2. Find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach 

where: 

n = 4

w=8 kg

(w1, w2, w3, w4) = (3, 4, 5, 6)

(p1, p2, p3, p4) = (2, 3, 4, 1)

Answer: Maximum Profit = 6 and Item Selected (1010) i.e p1 & p3 Selected

Multistage Graph Problem

This problem is solve by using dynamic programming method. Multistage Graph is a directed weighted graph. All vertices are divided into stages in such a way that vertex are connected to one edge to another edge.Note first stage and last stage are represented as a single vertex from source and sink of a graph.

Let we understand the working of multistage graph problem by the help of example.

 Dynamic Programming

Let we discuss about dynamic programming.Dynamic programming is an optimisation technique and we know Greedy method is also an optimisation  technique but both follow different strategy for solving the problem.

We know optimisation problem are those which gives either minimum results or maximum results.

In greedy method we define to follow predefine procedure to get optimal result. The  procedure is known to be optimal if we get follow the procedure to get the best result like: