# Knapsack problem

Discussion in 'C' started by arpit.jh001, Feb 15, 2012.

1. ### arpit.jh001New Member

Joined:
Feb 15, 2012
Messages:
10
0
Trophy Points:
0
Code:
```#include<iostream.h>

void print(float *a,int items)
{ float *temp=a;
for(int r=0;r<items;r++)
{  cout<<temp[r]<<"\t";
}
cout<<"\n";
}
void main()
{ int items,maxindex,W;
float max=0.0,temp;
float *w,*p;
float *x,*pw;
cout<<"Enter the number of items :";
cin>>items;
cout<<"\nEnter total size of Knapsack :";
cin>>W;
w = new float[items];
p = new float[items];
x = new float[items];
pw = new float[items];
cout<<"\n    Enter weight followed by profit on items \n";
cout<<"       ---------------------------- \n";
cout<<"        i       Weight      Profit          \n";
cout<<"       ---------------------------- \n";
for(int i=0;i<items;i++)
{  cout<<"\t"<<(i+1)<<"\t";
cin>>w[i];
cin>>p[i];
}
for(int k=0;k<items;k++)
{  pw[k]=(p[k]/w[k]);
x[k]=0.0;
}
cout<<"\n p/w: ";
print(pw,items);
for(int j=0;j<items;j++)
{ for(int l=0;l<items;l++)
{ temp=pw[l];
if(temp>max)
{ max=temp;
maxindex=l;
}
else
continue;
}
max=0.0;
pw[maxindex]=0.0;
if(w[maxindex]<=W)
{ x[maxindex] = 1.0;
W = W-w[maxindex];
}
else
{ if(W!=0)
{ x[maxindex]=W/w[maxindex];
W=0;
}
else
x[maxindex]=0.0;
}
}
cout<<"\n X :  " ;
print(x,items);
}
```
/*can anyone suggest me a better solution than this*/

Last edited by a moderator: Feb 15, 2012

Joined:
Aug 6, 2004
Messages:
3,012