An greedy approach to solve the fractional knapsack problem.

FractionalKnapsack.c

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

//Each item has a weight, value and a value/weight ratio.
 struct item{
	float weight;
	float value;
	float ratio;
}item[9],temp;

void knapsack(int n,float capacity, struct item item[]){
	
	float x[n], totVal = 0, remCap = 0;
	remCap = capacity; //Remaining capacity is = knapsack capacity before taking any item
	int i,j;
	for(i=0;i<n;i++)
		x[i] = 0;
	for(i=0;i<n;i++){
		//If weight of the item is greater than the reamaining capacity
		if(item[i].weight > remCap)
			break;
		else{	
			//The whole of the item is taken in the knapsack
			x[i] = 1;
			remCap -= item[i].weight;
			totVal += item[i].value;
		}
	}

	if( i< n){
		//How much portion of the item can be taken at max
		x[i] = remCap / item[i].weight;
		//only the value of that much portion of the item is added.
		totVal = totVal + (x[i] * item[i].value);
	}
	
	printf("\nThe items taken are: ");
	for(i=0;i<n;i++){
		printf("%f  ",x[i]);
	}

	printf("\nMaximum value : %f",totVal);
}



int main(){
	
	int i,j,n;
	float capacity;  //Maxumum knapsack capacity

	printf("\nEnter the number of items: ");
	scanf("%d",&n);
	for(i=0;i<n;i++){
		printf("\nWeight: ");
		scanf("%f",&item[i].weight);
		printf("Value: ");
		scanf("%f",&item[i].value);
	}
	printf("\nEnter the knapsack capacity: ");
	scanf("%f",&capacity);
	
	for(i=0;i<n;i++)
		item[i].ratio = (float)(item[i].value / item[i].weight);
	
	//Items are sorted in the decreasing order of their value/weight ratio
	for(i=0;i<n;i++){
		for(j=i+1;j<n;j++){
			if(item[i].ratio < item[j].ratio){
				temp = item[i];
				item[i] = item[j];
				item[j] = temp;
			}
		}
	}

	knapsack(n,capacity,item);
	return 0;
}