**Knapsack Problem using Backtracking**

Knapsack Problem using Backtracking is the important topic of the Analysis & Design of Algorithm. Moreover, freestudy9 has all kind of important information and topic related to it.

- We are given a certain number of objects and a knapsack.
- We shall suppose that we have n types of object and that an adequate number of objects of each type are available.
- This does not alter the problem in any important way. For i = 1, 2,…, n, an object of type i has a positive weight w
_{i}and a positive value v_{i}. - The knapsack can carry a weight not exceeding W.
- Our aim is to fill the knapsack in a way that maximizes the value of the included objects while respecting the capacity constraint.
- We may take an object or to leave it behind, but we may not take a fraction of an object.
- Suppose for concreteness that we wish to solve an instance of the problem involving four types of objects, whose weights are respectively 2, 3, 4 and 5 units, and whose values are 3, 5, 6 and 10. The knapsack can carry a maximum of 8 units of weight.

#### This can be done using backtracking by exploring the implicit tree shown below.

- Here a node such as (2, 3; 8) corresponds to a partial solution of our problem.
- The figures to the left of the semicolon are the weights of the objects we have decided to include, and the figure to the right is the current value of the load.
- Moving down from a node to one of its children corresponds to deciding which kind of object to put into the knapsack next. Without loss of generality, we may agree to load objects into the knapsack in order of increasing weight.
- Initially, the partial solution is empty.
- The backtracking algorithm explores the tree as in a depth-first search, constructing nodes and partial solutions as it goes.
- In the example, the first node visited is (2;3), the next is (2,2;6), the third is (2,2,2;9) and the fourth (2,2,2.2; 12).

#### As each new node is visited, the partial solution is extended.

- After visiting these four nodes, the depth-first search is blocked: node (2, 2, 2, 2; 12) has no unvisited successors (indeed no successors at all), since adding more items to this partial solution would violate the capacity constraint.
- Since this partial solution may turn out to be the optimal solution to our instance, we memorize it.
- Moreover, The depth-first search now backs up to look for other solutions.
- At each step back up the tree, the corresponding item removed from the partial solution.
- In the example, the search first backs up to (2, 2, 2; 9), which also has no unvisited successors; one step further up the tree, however, at node (2, 2; 6), two successors remain to visit.
- After exploring nodes (2, 2, 3; 11) and (2, 2, 4; 12), neither of which improves on the solution previously memorized, the search backs up one stage further, and so on.
- Exploring the tree in this way, (2, 3, 3; 13) found to be a better solution than the one we have, and later (3, 5; 15) is found to be better still.
- Since no other improvement made before the search ends, this is the optimal solution to the instance.

The algorithm can give as follows:

**function backpack(i, r) **

{Calculates the value of the best load that can construct using items of types i to n and whose total weight does not exceed r } b ← 0

{Try each allowed kind of item in turn}

for k ← i to n do

if w[k] ≤ r then

b ← max(b, v[k] + backpack(k, r – w[k]))

return b

Now to find the value of the best load, call backpack (1, W).

**Related Terms**

ADA Algorithms, Back Tracking, Articulation Point, Topological Sort

## Leave a Reply