Knapsack problem

arpit.jh001's Avatar, Join Date: Feb 2012
Go4Expert Member
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 shabbir; 15Feb2012 at 15:31.. Reason: Code blocks
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
http://en.wikipedia.org/wiki/Knapsack_problem

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