Greedy Knapsack Algorithm (code in c++)

Sunday, 21 August 2011 01:03
from-pwr[10] template-void-w[10]p[10]p_no[10]nm float-int
// Greedy Knapsack


/*Greedy Knapsack Program

Source code created by S.Kaarthikeyan from 

Computer Technology And Application Department from 

Coimbatore Institute of Technology

*/



# include 



int w[10],p[10],p_no[10],n,m;

float pwr[10];



template 

void swap(T *a,int i,int j)

{

	T temp;

	temp=a[j];

	a[j]=a[i];

	a[i]=temp;

	return;

}



void line()

{

	cout<<"\n";

	for(int i=0;i<80;i++)

		cout<<"=";

	cout<<"\n";

}



void display()

{

	line();

	cout<<"\n\t\t\t\tKnapsack\n";

	line();

	cout<<"\nNumber Of Products:\t"<	line();

	cout<<"\nSl.No\t\tWeight\t\tProfit\t\tPWR\n";

	line();

	for(int i=0;i		cout<	line();

}



void knapsack()

{

	int u,i;

	u=m;

	float x[10];

	for(i=0;i		x[i]=0;

	for(i=0;i	{

		if(w[i]>u)

			break;

		else

		{

			x[i]=1;

			u=u-w[i];

		}

	}

	if(i<=n)

		x[i]=(float)u/w[i];

	for(i=0;i	{

		for(int j=i+1;j		{

			if(p_no[i]>p_no[j])

			{

				swap(p_no,i,j);

				swap(x,i,j);

				swap(p,i,j);

			}

		}

	}

	float opt_solution=0;

	cout<<"\nThe Order is\n\n";

	cout<<"(";

	for(i=0;i		cout<	cout<<")";

	cout<<"\t\t(";

	for(i=0;i	{

		cout<		opt_solution=opt_solution+(p[i]*x[i]);

	}

	cout<<")";

	cout<<"\n\nThe optimal solution is\t"<}





void main()

{

	int i;

	cout<<"\nEnter the truck capacity:\t";

	cin>>m;

	cout<<"\nEnter the Number of items:\t";

	cin>>n;

	cout<<"\nEnter weights for "<	for(i=0;i	{

		p_no[i]=i+1;

		cout<<"\nProduct "<		cin>>w[i];

		cout<<"\nProfit:\t";

		cin>>p[i];

		pwr[i]=(float)p[i]/w[i];

	}

	display();

	for(i=0;i	{

		for(int j=i+1;j		{

			if(pwr[i]			{

				swap(p_no,i,j);

				swap(w,i,j);

				swap(p,i,j);

				swap(pwr,i,j);

			}

		}

	}

	display();

	knapsack();

	cout<<"\n\n";

}