IMPLEMENTATION OF KNAPSACK ALGORITHM PROGRAM

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;i
wp[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 )