greedyknapsack.c

#include<stdio.h>

float weight[50],profit[50],x[50];
int i,j;
void knapsack(float weight[],float profit[],int W,int n)
{
	int u;
	float tp=0;

	for(i=0;i<n;i++)
	{
		x[i]=0.0;
	}
	u=W;
	for(i=0;i<n;i++)
	{
		if(weight[i]>u)
		break;
		else
		{
			x[i]=1.0;
			tp=tp+profit[i];
			u=u-weight[i];
		}
	}
	if(i<n)
	{
		x[i]=u/weight[i];
		tp=tp+(profit[i]*x[i]);
	}
	printf("The result vector is:\t");
	for(i=0;i<n;i++)
	{
		printf("%f\t",x[i]);
	}
	printf("The total profit is:%f\t",tp);
}
void main()
{
	int n,W;
	float temp;
	printf("Enter number of items:\t");
	scanf("%d",&n);
	printf("Enter weight of knapsack:\t");
	scanf("%d",&W);
	for(i=0;i<n;i++)
	{
		printf("Enter weight of item %d:",i+1);
	    scanf("%f",&weight[i]);
	    printf("Enter profit of item %d:",i+1);
		scanf("%f",&profit[i]);
	}
	for(i=0;i<n;i++)
	{
		x[i]=profit[i]/weight[i];
	}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(x[j]>x[i])
			{
				temp=x[j];
                x[j]=x[i];
                x[i]=temp;

                temp=weight[j];
                weight[j]=weight[i];
                weight[i]=temp;

                temp=profit[j];
                profit[j]=profit[i];
                profit[i]=temp;
			}
		}
	}
	knapsack(weight,profit,W,n);
}