KNAPSACK Algorithm Implementation Program in C

IMPLEMENTATION OF KNAPSACK ALGORITHM

PROGRAM:

#include
#include
#include
int w[]={18,15,10};
int p[]={25,24,15};
int m=20;
int n=3;
int weight[10];
void main()
{
int i,u,a[10];
float t1,t2,t,wp[10],max;
float profit[]={0.0,0.0,0.0},tp=0.0,tpl=0.0,x[4];
clrscr();
cout<<"\n\t\t knapsack problem using greedy method";
cout<<"\n\t\t...........";
for(i=0;iwp[i]=(float)p[i]/w[i];
for(i=0;i{
for(int j=i+1;j{
if(wp[i]{
t1=p[i];
p[i]=p[j];
p[j]=t1;
t2=w[i];
w[i]=w[j];
w[j]=t2;
t=wp[i];
wp[i]=wp[j];
wp[j]=t;
}
}
}
u=m;
for(i=0;i{
profit[i]=0.0;
x[i]=0.0;
}
for(i=0;i{
if(w[i]>u)
break;
x[i]=1.0;
u=u-w[i];
profit[i]=p[i];
tp=tp+profit[i];
}
if(i{
x[i]=(float)u/w[i];
profit[i]=x[i]*p[i];
tp=tp+profit[i];
}
cout<<"\n object \t domain included \t profit gained";
for(i=0;i{
cout<<"\n"<cout<cout<<"\t\t\t"<}
cout<<"\n total profit gained"<tpl=0.0;
u=m;
for(i=0;i{
x[i]=0.0;
weight[i]=0.0;
}
for(i=0;i{
if(w[i]>u)
break;
x[i]=1.0;
u=u-w[i];
weight[i]=w[i];
tpl=tpl+weight[i];
}
if(i{
cout<<"\t\t\t"<}
cout<<"\n total profit gained"<tpl=0.0;
u=m;
for(i=0;i{
x[i]=0.0;
weight[i]=0.0;
}
for(i=0;i{
if(w[i]>u)
break;
x[i]=1.0;
u=u-w[i];
weight[i]=w[i];
tpl=tpl+weight[i];
}
if(i{
x[i]=(float)/p[i];
weight[i]=x[i]*p[i];
tp1=tp1+weight[i];
}
cout<<”\n\n\n object \t partial included \n profit gained”;
for(i=0;i{
cout<<”\n”<cout<cout<<”\t\t\t”<cout<<”\n\n\n total weight gained=”<getch();
}











OUTPUT:

Knapsack problem using greedy method
...........
object domain included profit gained
1 1 24
2 0.5 7.5
3 0 0
total profit gained31.5


object portion included profit gained
1 1 15
2 0.33 5
3 0 0
total weight gained=20






CIET college Programs,LAB Programs for Engineering Students,DAA LAB Programs,DSA LAB Programs,Remoboys,karthik,Remokn,Student3k,programs source code,Design Analysis And Algorithms LAB Programs,Data Structures and Algorithms LAB Programs,LAB Codings,Coimbatore Institute of Engineering and Technology ( CIET )