C program of Knapsack problem using Backtracking

C program of Knapsack problem using Backtracking

1482
4
SHARE

C program of knapsack problem using backtracking : The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

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

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.

Let us see how to write approach. Before going through first understand the variables definition that i have used in the code.

n   – Total no. of items available

w[] – Weight of each item

p[] – Profit of each item

m   – Maximum Capacity of the Sack

unit[] – Profit of each item per Unit p[]/w[]

x[] – Final list of items put into the Sack

y[] – Intermediate list of selected items

fp  – Final Profit

fw  – Final Weight

cp  – Current Profit

cw  – Current Weight

C program of knapsack problem using backtracking approach :

#include <stdio.h>
#include <conio.h>
#define max 10

int w[max],i,j,p[max];
int n,m;
float unit[max];
int y[max],x[max],fp=-1,fw;
void get()
{
printf("----------------------------------------------------------------------\n");
printf("-------------------made by C code champ ------------------------------\n");
printf("----------------------------------------------------------------------\n");
printf("\n\n\t KNAPSACK PROBLEM SOLUTION IN C\n");     
printf("\n Enter total number of items: ");
scanf("%d",&n);
printf("\n Enter the Maximum capacity of the Sack: ");
scanf("%d",&m);
for(i=0;i<n;i++)
   {
   printf("\n Enter the weight of the item %d : ",i+1);
   scanf("%d",&w[i]);
   printf("\n Enter the profit of the item %d : ", i+1);
   scanf("%d", &p[i]);
   }
}

void show()
{
float s=0.0;
printf("\n\tItem\tWeight\tCost\tUnit Profit\tSelected ");
for(i=0;i<n;i++)
printf("\n\t%d\t%d\t%d\t%f\t%d",i+1,w[i],p[i],unit[i],x[i]);
printf("\n\n The Sack now holds following items : ");
for(i=0;i<n;i++)
if(x[i]==1)
   {
   printf("%d\t",i+1);
   s += (float) p[i] * (float) x[i];
   }

printf("\n Maximum Profit: %f ",s);
}

/*Arrange the item based on high profit per Unit*/
void sort()
{
int t,t1;
float t2;
for(i=0;i<n;i++)
unit[i] = (float) p[i] / (float) w[i];
for(i=0;i<n-1;i++)
   {
   for(j=i+1;j<n;j++)
      {
      if(unit[i]  < unit[j])
         {
         t2 = unit[i];
         unit[i] = unit[j];
         unit[j] = t2;
         t = p[i];
         p[i] = p[j];
         p[j] = t;
         t1 = w[i];
         w[i] = w[j];
         w[j] =t1;
         }
      }
    }
}

float bound(float cp,float cw,int k)
{
float b = cp;
float c = cw;
for(i=k;i<=n;i++)
{
   c = c+w[i];
   if( c < m)
      b = b +p[i];
   else
   return (b+(1-(c-m)/ (float)w[i])*p[i]);
}
return b;
}

void knapsack(int k,float cp,float cw)
{
 if(cw+w[k] <= m)
   {
   y[k] = 1;
   if(k <= n)
      knapsack(k+1,cp+p[k],cw+w[k]);
   if(((cp+p[k]) > fp) && ( k == n))
      {
      fp = cp+p[k];
      fw = cw+w[k];
      for(j=0;j<=k;j++)
      x[j] = y[j];
      }
    }
if(bound(cp,cw,k) >= fp)
{
 y[k] = 0;
 if( k <= n)
 knapsack(k+1,cp,cw);
 if((cp > fp) && (k == n))
   {
   fp = cp;
   fw = cw;
   for(j=0;j<=k;j++)
   x[j] = y[j];
   }
}
}

int main()
{
get();
printf("\n The Sack is arranged in the order\n");
sort();
knapsack(0,0.0,0.0);
show();
getch();
}

We hope you all have enjoyed the using backtracking. If you have any issues with the code or logic, ask us in form of comments.

 

4 COMMENTS

    • Hola amigo,

      Tu programa no corre, ya intenté encontrar el error y mejorarlo pero aún no lo he conseguido. Podrías indicarme en dónde está el error. De hecho, los errores que me envian son:
      [Warning] converting to “int” from float

LEAVE A REPLY