Knapsnack-Greedy

 #include<iostream.h>  
 #include<conio.h>  
 float w[100],v[100],x[100],wt,wgt[100];  
 class greed  
 {  
      private:  
           int i,j,n;  
           float r[100],f,total,t,rat,pro,wei,op,opti;  
      public:  
           void getdata();  
           void ratio();  
           void profit();  
           void weight();  
           void optimal();  
 };  
 void greedy(int n)  
 {  
      int wgt,i;  
      for(i=0;i<n;i++)  
           x[i]=0;  
      wgt=i=0;  
      while(wgt<wt)  
      {  
           if(wgt+w[i]<=wt)  
           {  
                x[i]=1;  
                wgt+=w[i];  
           }  
           else  
           {  
                x[i]=(wt-wgt)/w[i];  
                wgt+=(x[i]*w[i]);  
           }  
           i++;  
      }  
 }  
 void greed:: getdata()  
 {  
      cout<<"Enter no of objects : ";  
      cin>>n;  
      cout<<"Enter the capacity of the bag : ";  
      cin>>wt;  
      for(i=0;i<n;i++)  
      {  
           cout<<"Weight = ";  
           cin>>w[i];  
           cout<<"Profit = ";  
           cin>>v[i];  
           r[i]=v[i]/w[i];  
      }  
 }  
 void greed:: ratio()  
 {  
      cout<<endl<<"\t\t\tGREEDY BY RATIO\n";  
      for(i=0;i<n;i++)  
      {  
           for(j=i+1;j<n;j++)  
           {  
                if(r[i]<r[j])  
                {  
                     t=w[i];w[i]=w[j];w[j]=t;  
                     t=v[i];v[i]=v[j];v[j]=t;  
                     t=r[i];r[i]=r[j];r[j]=t;  
                }  
           }  
      }  
      greedy(n);  
      for(i=0;i<n;i++)  
      {  
           cout<<"\nWeight "<<w[i];  
           cout<<"\tProfit "<<v[i];  
           cout<<"\tRatio "<<r[i];  
           cout<<"\tFraction "<<x[i];  
           total+=(x[i]*v[i]);  
      }  
      cout<<"\nFeasible profit = "<<total;  
      rat=total;  
      getch();  
      total=0;  
 }  
 void greed:: profit()  
 {  
      cout<<endl<<"\t\tGREEDY BY PROFIT\n";  
      for(i=0;i<n;i++)  
      {  
           for(j=i+1;j<n;j++)  
           {  
                if(v[i]<v[j])  
                {  
                     t=w[i];w[i]=w[j];w[j]=t;  
                     t=v[i];v[i]=v[j];v[j]=t;  
                     t=r[i];r[i]=r[j];r[j]=t;  
                }  
           }  
      }  
      greedy(n);  
      for(i=0;i<n;i++)  
      {  
           cout<<"\nWeight "<<w[i];  
           cout<<"\tProfit "<<v[i];  
           cout<<"\tRatio "<<r[i];  
           cout<<"\tFraction "<<x[i];  
           total+=(x[i]*v[i]);  
      }  
      cout<<"\nFeasible profit = "<<total;  
      pro=total;  
      getch();  
      total=0;  
 }  
 void greed:: weight()  
 {  
      cout<<"GREEDY BY WEIGHT\n";  
      for(i=0;i<n;i++)  
      {  
           for(j=i+1;j<n;j++)  
           {  
                if(w[i]<w[j])  
                {  
                     t=w[i];w[i]=w[j];w[j]=t;  
                     t=v[i];v[i]=v[j];v[j]=t;  
                     t=r[i];r[i]=r[j];r[j]=t;  
                }  
           }  
      }  
      greedy(n);  
      for(i=0;i<n;i++)  
      {  
           cout<<"\nWeight "<<w[i];  
           cout<<"\tProfit "<<v[i];  
           cout<<"\tRatio "<<r[i];  
           cout<<"\tFraction "<<x[i];  
           total+=(x[i]*v[i]);  
      }  
      cout<<"\nFeasible profit = "<<total;  
      wei=total;  
      getch();  
 }  
 void greed:: optimal()  
 {  
      if(rat>pro)  
           op=rat;  
      else  
           op=pro;  
      if(op>wei)  
           opti=op;  
      else  
           opti=wei;  
      cout<<"\n\n\n  
 OPTIMAL SOLUTION IS "<<opti;  
      getch();  
 }  
 void main()  
 {  
      clrscr();  
      greed s;  
      cout<<"KNAPSACK PROBLEM\n";  
      s.getdata();  
      s.ratio();  
      s.profit();  
      s.weight();  
      s.optimal();  
      getch();  
 }