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:

 Huffman Coding

It is a Greedy Approach.It is an compression technique used to encode compress data. It is used for reducing the size of data of message. If we store the data on the file than we need compression to reduce the size of file. When the the data is send over a network than the data is compress and send to reduce the cost of transmission.

 B+ TREE

B+ Tree is a B-Tree of order m which satisfy following condition.

1. All leaf node are at same level.

2. All intermediate nodes except the roots can have at most 'm' non - empty children's and can have as few as integer value of m/2.

3. Each node of B-Tree has are less key than its number of children and keys are inserted in a search tree fashion.

4. The root of B-Tree can have at most 'm' non-empty children and can have as few as two if root is alone.

5. Each intermediate key has a similar copy in its successor or predecessor leaf.

6. All leaf are connected through a direct link in a link list fashion.

 THREADED BINARY SEARCH TREE

THREADS:  We will replace certain NULL entries by spacial pointer which point to nodes higher in tree.These special pointer are called threads.

LINKS: Those pointers which contain the address of its successor node in tree is called link.

EXAMPLE:

BINARY SEARCH TREE

Binary Search Tree is a binary tree in which parent data is always greater than its left child data and always less than its right child data and again all sub tree are Binary tree.

 2-3 TREE

Let we understand 2-3 tree by some points:

📢 It is a basically a B Tree of order 3.

📢 It has maximum 2 children and maximum 2 key values.

📢 It is a search tree.

📢 To keep the height of a binary search tree a 2-3 tree were developed.

📢 A 2-3 tree is a binary search tree that can have the following nodes

    1. Leaf Nodes

    2. 2- Nodes

    3. 3-Nodes

                 PREORDER  | TRAVERSING TECHNIQUE

A Short Trick

Let we understand the PREORDER TRAVERSING TECHNIQUE from the following binary tree.

Suppose we have any binary tree such as:

80 , 50 , 100 , 45 , 95 , 110 , 47 , 99 , 115 , 97

Now we find  Preorder sequence of following binary tree.

First mark every node at the right side of node like

 POSTORDER  | TRAVERSING TECHNIQUE

A Short Trick

Let we understand the POSTORDER TRAVERSING TECHNIQUE from the following binary tree.

Suppose we have any binary tree such as:

80 , 50 , 100 , 45 , 95 , 110 , 47 , 99 , 115 , 97

Now we find  Postorder sequence of following binary tree.

First mark every node at the right side of node like

 INORDER | TRAVERSING TECHNIQUE

Short Trick

Let we understand INORDER technique with the help of example:

Suppose we have any binary tree such as:

80 , 50 , 100 , 45 , 95 , 110 , 47 , 99 , 115 , 97

Now we find  Inorder sequence of following binary tree.

First mark every node at the bottom like

Breadth First Search is a Graph Traversal Methods.It is a technique used to search a vertex in a graph breadth wise. It is also used to decide the order of vertices to be visited in the search process.

Breadth First Search(BFS) produce a spanning tree as a final result is graph without loops.We use Queue data structure with maximum size of total number of vertices in the graph to implement BFS of a graph.

📌Hello friends! In this post I am going to explain about Depth First Search (DFS).What is the algorithm/ How we trace algorithm by the help of example. 

Depth First Search is a Graph Traversal Methods.It is a technique used to search a vertex in a graph. It is also used to decide the order of vertices to be visited in the search process.

Let we understand What is B-Tree:

B-Tree  is a multi way search tree of order 'm' which satisfy the following conditions.

1. All leafs are at same level.

2. All intermediate nodes except the roots can have at most 'm' non-empty children and can have as few as integer value of m/2.

3. Each node of B-tree has one less key than its number of children and key are inserted in a search tree fission.

4. The root of B-Tree can have at most 'm' non-empty children and can have as few as two , if root is alone.

📌Highlights: Hi Friends ! In this post , I discuss about Dijkstra Algorithm which is also known as Single Source Shortest path Algorithm using greedy approach.I will explain all the working procedure of algorithm by taking an example.

Let we understand what is it,

Dijkstra algorithm is also known as single source shortest path  algorithm. The main purpose of this algorithm is to find shortest path form a given graph.

This approach is very simple. In this approach we simply merge those set of files / elements which have smaller values.it follow optimal search pattern.

For understanding Optimal Merge Problem, Let we understand simple merging.

Suppose if we have two shorted list. Marge these two list and create a third list.

Strassen's Matrix Multiplication  

is basically used to improve the process of simple matrix multiplication.For this 

👉 How simple matrix multiplication done normally. 

👉How divide and conquer strategy is apply to solve matrix multiplication problem. 

👉What Strassen's Matrix Multiplication had done to improve matrix multiplication using divide and conquer strategy ?

Divide and conquer strategy simply says that if any problem is big and easy to solve than that problem is divided into sub problems , process it and get solution, But if the sub problem is also big and not easy to solve than sub problem is divided sub sub problems if it will not solve than do the same thing again on that sub sub problem until we are not getting solution.

📌Highlights: Hi Friends ! In this post I am going to explain the concept of Binary Search , How this will work, How to write Binary Search Algorithm, How to write the procedure of Binary Search in C.How to find their complexity and example. 

Binary Search method is based on divide and conquer strategy. In Binary search first we find mid position element of array and point it to the (MID) index pointer. Now we compare searching element (S) to MID element. Such that 

If MID position element is greater than (S) then we discard second part of array and continue binary search with first part from (LOW) to (MID-1).

If MID position is less than (S) then we discard first part of array and continue Binary Search with second part from (MID+1) to (HIGH).

Merge sort is based on divide and conquer strategy in which first we try to divide array of N elements to N - sorted array of single elements then merging process merge these sorted array into one sorted array.

Let we understand by the help of an example:

Suppose we have an array of 8 elements such as:

Now we want to sort these elements using merge sort.