6. Write a program to demonstrate Fractional Knapsack problem using greedy solution.
// Algorithm: Fractional_Knapsack (Greedy Approach)
// Input: W: Maximum capacity of knapsack (integer), arr[]: Array of Items (each with value,
weight), n: Number of items (integer)
// Output: Maximum achievable value by selecting fractional parts of items, without exceeding
capacity W.
Step 1: For each item in arr:
Step 2: Calculate ratio ← value / weight
Step 3: Sort arr[] in descending order of ratio
Step 4: Initialize totalValue ← 0.0
Step 5: For each item in sorted arr:
Step 6: If item.weight ≤ W:
Step 7: Add item.value to totalValue
Step 8: Subtract item.weight from W
Step 9: Else:
Step 10: Add (ratio × remaining W) to totalValue
Step 11: Break loop
Step 12: Return totalValue
#include< stdio.h>
#include< conio.h>
struct Item
{
int value, weight;
float ratio;
};
float fractionalKnapsack(int W, struct Item arr[], int n)
{
int i, j;
struct Item temp;
float totalValue = 0.0;
for(i = 0; i < n; i++)
arr[i].ratio = (float)arr[i].value / arr[i].weight;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j].ratio < arr[j+1].ratio)

{

temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
for (i = 0; i < n; i++)
if (arr[i].weight <= W)
{
totalValue += arr[i].value;
W -= arr[i].weight;
}

else
{
totalValue += arr[i].ratio * W;
break;
}
return totalValue;
}
void main()
{
int W, n, i;
struct Item arr[20];
clrscr();
printf("Enter maximum capacity of knapsack: ");
scanf("%d", &W);
printf("Enter number of items: ");
scanf("%d", &n);
for(i = 0; i < n; i++)
{
printf("Enter value and weight for item %d: ", i+1);
scanf("%d %d", &arr[i].value, &arr[i].weight);
}
printf("Maximum value = %.2f", fractionalKnapsack(W, arr, n));
getch();
}