KNAPSACK PROBLEM

C PROGRAM TO IMPLEMENT KNAPSACK PROBLEM  USING BACKTRACKING

#include<stdio.h>

#include<conio.h>

float final_profit=-1.0;

intp[9]={0,11,21,31,33,43,53,55,65};

int w[9]={0,1,11,21,23,33,43,45,55};

int m=110;

int n=8;

int temp[9],x[9];

float final_wt=-1.0;

float bound_calculation(int cp,int cw,int k)

{

int ub,c,i;

ub=cp;

c=cw;

for(i=k+1;i<n;i++)

{

c=c+w[i];

if(c<m)

ub=ub+p[i];

else

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

}

return ub;

}

void BK(int k,int cp,int cw)

{

int new_k,new_cp,new-cw,j;

//Generate left child

if(cw+w[k]<=m)

{

temp[k]=1;

if(k<n)

{

new_k=k+1;

new_cp=cp+p[k];

new_cw=cw+w[k];

BK(new_k,new_cp,new_cw);

}

if((new_cp>final_profit)&&(k==n))

{

final_profit=new_cp;

final_wt=new_cw;

for(j=1;j<k;j++)

x[j]=temp[j];

}

}

//Generate right child

if(Bound_calculation(cp,cw,k)>==final_profit)

{

temp[k]=0;

if(k<n)

BK(k+1,cp,cw);

if((cp>final_profit)&&(k==n))

{

final_profit=cp;

final_wt=cw;

for(j=1;j<n;j++)

x[j]=temp[j];

}

}

}

void main()

{

int i;

clrscr();

printf("\n\t Knapsack problem using backtracking algorithm \n");

printf("\n Capacity of knapsack=%d",m);

printf("\n\n Profit\t Weight");

printf("\n-------------------------------");

for(i=1;i<=n;i++)

printf("\n%d\t%d",p[i],w[i]);

printf("\n-------------------------------");

BK(1,0,0);

printf("\n Following items are selected from knapsack...");

for(i=1;1<=n;i++)

{

if(x[i]==1)

printf("\n\t\t Item %d",i);

}

printf("\n\n Final Weight =%0.2f",final_wt);

printf("\n Final Profit=%0.2f",final_profit);

getch();

}

OUTPUT:

Knapsack problem using Backtracking algorithm

capacity of knapsack=110

Profit weight

-----------------------------

11     1

21     11

31     21

33     23

43     33

53     43

55     45

65     55

-----------------------------

Following item are selected from knapsack...

Item 1

Item 2

Item 3

item 5

Item 6

Final weight=109.00

final Profit=159.00