KNAPSACK PROBLEM USING BACKTRACKING

KNAPSACK PROBLEM USING BACKTRACKING

This article explains about solving of knapsack problem using backtracking method.

 Concept:

            In solving of knapsack problem using backtracking method we mostly consider the profit but in case of dynamic programming we consider weights.

Concept of backtracking:

            The idea of backtracking is to construct solutions one component at a time and evaluate such partially constructed solutions. This partially constructed solution can be developed further without violating the problem constraints.

            It is convenient to implement this kind of processing by constructing a tree of choices being made called the "State Space Tree". Its root represents an initial state before the search for the solution begins. The nodes of the first level in the tree represent the choices for the first component of a solution and the nodes of a second level represent the choices for the second component and so on.

            A node in the state space tree is promising if it corresponds to the partials constructed solution that may lead to the complete solution otherwise the nodes are called non-promising. Leaves of the tree represent either the non- promising dead end or complete solution found by the algorithm.

 

Concept of Knapsack:

            The knapsack is nothing but a sack where in which we need to place the given items according to the capacity of the knapsack. In case of backtracking we consider the profits but in dynamic programming we consider weights.

 

Algorithm:

            Bound (CP, CW, K)

            {

                        b=CP, c=CW;

                        for i=k+1 to n dp

                        {

                                    c=c + w [i];

                                    if (c<m) then

                                    b= b + p[i];

                                    else

                                    return b+(1-(c-m)/w[i])*p[i]                             ;

                                    return b;

                        }

            }

Consider:

            CP=Current Profit;       CW=Current Weight; K= Index; m=Capacity of Knapsack;

 

Example:

            Profits P1=10, P2=10, P3=12, P4=18.

            Weights W1= 2, W2= 4, W3= 6, W4=9;

            m=15;

            n=4;

           

Tracing:

When,  i=1 C=2; b=10;

When,  i=2 w[2]=4 so, c=c + w[2] c= 2+4= 6  so c= 6 if 6<15  condition gets true so b=10+10=20;

c=6;

b=20

When,  i=3 w[3]=6 so, c=c + w[3] c= 6+6= 12  so c= 12 if 12<15  condition gets true so b=20+12=32;

c=12;

b=32

When,  i=4 w[4]=9 so, c=c + w[4] c= 12+9= 21  so c= 21 if 21<15  condition gets FALSE    so b+(1-(c-m)/w[i])*p[i] is 32+(1-(21-15)/9)*18=38

c=21;

b=38;

Here we got the maximum profit as 38.

To obtain this maximum capacity we need to consider the Item 4 first then Item 2 then Item 1 that is 18+10+10 = 38.

Read more: http://www.articlesbase.com/computers-articles/knapsack-problem-using-backtracking-2099286.html#ixzz1NAexAEAv 
Under Creative Commons License: Attribution