//////////////////////////////////////////////////////////////////////////////////////////////////
//       This program is designed by : Ne'matollah Kamalfar & shahin Noormah  			//
//			       professor: Mrs. Tadayon						//
//			          Knapsack Algorithm						//
//       	              compiled by Borland C++ 5						//
//////////////////////////////////////////////////////////////////////////////////////////////////

#include<iostream.h>
#include<conio.h>

struct knapsack
{
   int n;
   int* w;
   int* p;
   int* itemNum;

}s;

void Knapsack(int capacity,knapsack& ksack)
{
   int i;
	float* value=new float[capacity];
	ksack.itemNum=new int(ksack.n);

	for(i=0;i<ksack.n;i++)
		ksack.itemNum[i]=i+1;


	for(i=0;i<ksack.n-1;i++)
	   for(int j=0;j<ksack.n-1-i;j++)
	   {
		int t1;
		int t2;
		int t3;
		if (((float)ksack.p[i])/ksack.w[i]<((float)ksack.p[i+1])/ksack.w[i+1])
		{
		   t1=ksack.p[i+1];
		   t2=ksack.w[i+1];
		   t3=ksack.itemNum[i+1];
		   ksack.p[i+1]=ksack.p[i];
		   ksack.w[i+1]=ksack.w[i];
		   ksack.itemNum[i+1]=ksack.itemNum[i];
		   ksack.p[i]=t1;
		   ksack.w[i]=t2;
		   ksack.itemNum[i]=t3;
		   }//if
      }//for

   for(i=0;i<ksack.n;i++)
      value[i]=0.0;

   float maxprofit=0.0;
   cout<<"\nSelected objects and their velus:\n";
   cout<< "Item      value\n";
   cout<<"----------------";
	for(i=0;i<ksack.n;i++)
	{
	   if(ksack.w[i]>capacity)
		   break;
      value[i]=1.0;
	   capacity=capacity-ksack.w[i];
      maxprofit+=ksack.p[i];
	   cout<<"\n "<<ksack.itemNum[i]<<"          "<<value[i];
      cout <<"\n----------------";

   }//for
   if(i<=ksack.n-1)
	{
	   value[i]=(float)capacity/ksack.w[i];
		cout<<"\n "<<ksack.itemNum[i]<<"          "<<value[i];
	   maxprofit=maxprofit+(value[i]*ksack.p[i]);
      cout << "\n";
   }//if
   else cout << "\r";
   cout<<"----------------";
   cout<<"\nMaxprofit: "<<maxprofit;
}//Knapsack

void main()
{
   clrscr();
   int N,W;

   cout<<"Enter number of items: ";
   cin>>N;
   s.n=N;
   s.w=new int [N];
   s.p=new int [N];

   cout<<"Enter Maximum capacity of Knapsack: ";
   cin>>W;
   cout<<"\nPlease Enter";
   cout<<"\n";
   for(int i=0;i<N;i++)
   {
	cout<<"\nItem"<< (i+1) <<" profit: ";
	cin>>s.p[i];
	cout<<"\nItem"<< (i+1) <<" weight: ";
	cin>>s.w[i];
	cout<<"\n" ;
   }//for

   Knapsack(W,s);
   getch();
}//main