Use the Backtracking algorithm for the 01 Knapsack problem t

Use the Backtracking algorithm for the 0-1 Knapsack problem to maximize the profit for the following problem instance. Show the actions step by step.

Solution

What is Backtracking Solution :

   Backtracking Solution is an recursive solution.
   It is an Exhaustive method Because it Consider all the possible solution and
   Then select the best solution.

In above mentioned question :

   We have total 5 items
   in our algorithm There Profit is represented by array P ;
   each P[i] represents an (i+1)th item\'s profit {because indexing start from 0 }
   so
       P[0] -----------> 1st items profit
       P[1]------------>2nd items profit
       P[2] -----------> 3rd items profit
       P[3]------------> 4th items profit
       P[4] -----------> 5th items profit

   Weight is represnted by array W :

   each W[i] represents an (i+1)th item\'s profit {because indexing start from 0 }
   so
       W[0] -----------> 1st items weight
       W[1]------------>2nd items weight
       W[2] -----------> 3rd items weight
       W[3]------------> 4th items weight
       W[4] -----------> 5th items weight

   we are using another array X whose length is equal to number of items that is in our case 5;
   this array X keeps the information whether some item is selected or not

   if x[i] = 0 it means (i+1) is not choosen ;
   if x[i] = 1 it means (i+1) is choosen;

   so array X: {0,0,1,1,0}
   shows that item     3rd and 4th is choosen for solution

   in our algorithm we are finding all the possible solution that is for n items finding all the
   2^n subsets that can be solutions for the problem
   then finding the best solution out of these 2^n which follow the constraints.
  

   Algorithm ::
  
#include <iostream>
using namespace std;
int maxprofit = 0;
int max_weight = 0;
int opx[5]={0};
int P[] = {20,30,35,12,3};
int W[] = {2,5,7,3,1};
int index = 4;
int knapsack(int X[],int l)
{
   //cout<<\"knapsack called\"<<endl;
   if(l>index)
   {
       // find profit of all the selected items
       // X[i] == 1 means item is selected
       int cprofit = 0; // profit of this solution
       int cweight = 0; // weight of this solution
       for(int i=0;i<index+1;++i)
       {
           if(X[i]==1){
                   cprofit = cprofit + P[i];
                   cweight = cweight + W[i];
           }
       }
       //check whether this solutions weight is under the weight limit and
       // and its profit is greater than the max profit
   //   cout<<cweight<<\" == \"<<max_weight<<\" \"<<cprofit<<\" \"<<maxprofit<<endl;
       if(cweight<=max_weight && cprofit > maxprofit)
       {
           // update the max profit
           maxprofit = cprofit;
           // update the opx final solution array
           for(int i=0;i<index+1;++i)
           {
               opx[i]=X[i];
           }
          
       }
      
   }
   else
   {
       // recursive call
       // two possiblities can be possible
       // if we select item
           X[l] = 1; // item l is selected
           //call the knapsack funtion
           knapsack(X,l+1);
           // if we dont select the item
           X[l] = 0;
           knapsack(X,l+1);
          
      
   }
}
int main() {
   // your code goes here
   int X[]={0,0,0,0,0}; // initially all are zero nothing is selected
   //call the knapsack function
   max_weight = 9 ; // set the maximum weight knapsack can have
   knapsack(X,0);
   cout<<maxprofit<<endl;
   for(int i=0;i<index+1;++i)
   {
       if(opx[i]==1)
       {
           cout<<\"Item number : \"<<i+1<<endl;
       }
   }
  
   return 0;
}