Knapsack & Backtracking | Design & Analysis of Algorithms | post 2

Some important applications of dynamic programming.

0/1 knapsack problem-

In this problem , knapsack is just like a bag and we have to fill items in this bag by making sure two things -

1) Value of the bag should be maximum.

2) Wight of the bag should be minimum. 

" In numerical problems, weight is given in numeric form so be sure that the weight of knapscak should not be exceeded from given Total weight. "

Differences between knapsack and 0/1 knapsack problem is that we can split items in parts for the first one but we cant split item in 0/1 knapsack problem. 0 stands for item is not picked and 1 stands for item is picked inside the knapsack.

This is a formula for putting item in knapsack with values -

Max { ([i].value with given weight + j-n) , [i-1].value from knapsack table) }

Where ,

           i = row number in knapsack table

           j = values in columns of knapsack table

          n = number of backward steps to the      knapsack table( column wise)

Example 

Total weight = 7 

 Set of weights are given = { 1, 3, 4, 5 }

 Set of values respective wts = { 3, 4, 7, 9 }

 So you have to fill all the items in knapsack like that the weight should be minimum and the value of knapsack should be maximum.

Backtracking -

It is used to solve a problem in which a sequence of objects is chosen from a specified set so that sequence satisfy some criteria.

When is it used ?

1. Difference choices are given and from these choices we have to select a decision.

2. When a sufficient information is not avialable on best choice.

3. Each decision leads to new set of choices.

4. Some sequences of choices may be the solution.

How is it performed ?

Backtracking is a systematic method of trying out various sequences of decisions until you find out that works (solution).

Block diagram (Backtracking) -

There are two type of constraints in Backtracking.

1. Implicit - means how each element in tuple should be related.

2. Explicit - means rules which are restricted choosen from a given set.

Applications of Backtracking -

1. N queens problem
2. Sum of subsets
3. Graph colouring
4. Hemiltonian problem

These all applications are dictate in further posts.

If have any queries, just drop a comment or feel free to connect at -
https://www.instagram.com/kavyansh.pandey

Thanking you.