Fractional Knapsack : Greedy approach

/*
* Status: Tested OK
* Title: Fractional Knapsack using Greedy Approach
* Name: Akshay Thakare
*/

#include <stdio.h>
#include <stdlib.h>

double *p, *w, m;		//Array of profits, weights and max sack capacity
int n;				//Array size
double cp,cw;			//cumulative profit and weight (for calc)

void sort()
{
	int i,j;
	double temp_swap;

	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if((p[i]/w[i])>(p[j]/w[j]))
			{
				temp_swap = p[i];
				p[i]=p[j];
				p[j]=temp_swap;
				
				temp_swap = w[i];
				w[i]=w[j];
				w[j]=temp_swap;
			}
		}
	}
}

void f_knap()
{
	int i;
	cp = 0;
	cw = 0;
	
	sort();
				//Quick Sort can be used to futher enhance computation speed
	for(i=0;i<n;i++)
	{
		if ((cw+w[i])<=m)
		{
			cw += w[i];
			cp += p[i];
		}
		else
		{
			cp = cp + (p[i]/w[i])*(m-cw);			//VIMP: cp should come before cw as cw is changing
			cw = cw + (w[i]/w[i])*(m-cw);
			return;
		}
	}
	return;
}

int main()
{
	int i;
	n=6;m=13;
	
	printf("\nEnter the number of objects under consideration : ");
		scanf("%d",&n);
	printf("\nEnter max sack capacity = ");
		scanf("%lf",&m);
	
	p = malloc(n*sizeof(double));
	w = malloc(n*sizeof(double));

	printf("\nEnter the profits and weights below\n");
	for(i=0;i<n;i++)
	{
		printf("\nEnter the profit and weight for item %d below : \n",i+1);
		scanf("%lf%lf",&p[i],&w[i]);
	}
	
	f_knap();

	printf("\nMaximum profit = %0.2lf",cp);
	
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s