Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Knapsack problem (http://www.go4expert.com/forums/knapsack-problem-t27805/)

 arpit.jh001 15Feb2012 15:07

Knapsack problem

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*/

 xpi0t0s 16Feb2012 18:20

Re: Knapsack problem

http://en.wikipedia.org/wiki/Knapsack_problem

Found by Googling "knapsack problem" and it was the top hit.

 All times are GMT +5.5. The time now is 04:34.