Go4Expert

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 10:07.