C program for the Fractional Knapsack Algorithm for the flood relief scenario, where:
Some items are divisible (like food/water) — so we can take partial amounts.
Some items are indivisible (like medical kits) — so we can only take whole items.
We maximize the utility value given the boat’s weight limit.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
char name[50];
float weight;
float value;
int divisible; // 1 = divisible, 0 = indivisible
float ratio; // value-to-weight ratio
} Item;
void sortByRatio(Item items[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (items[j].ratio < items[j + 1].ratio) {
Item temp = items[j];
items[j] = items[j + 1];
items[j + 1] = temp;
}
}
}
}
int main() {
int n;
float W;
printf("Enter number of relief items: ");
scanf("%d", &n);
Item items[n];
for (int i = 0; i < n; i++) {
printf("\nEnter name of item %d: ", i + 1);
scanf("%s", items[i].name);
printf("Enter weight (kg): ");
scanf("%f", &items[i].weight);
printf("Enter utility value: ");
scanf("%f", &items[i].value);
printf("Is the item divisible? (1 = Yes, 0 = No): ");
scanf("%d", &items[i].divisible);
items[i].ratio = items[i].value / items[i].weight;
}
printf("\nEnter maximum weight capacity of the boat (kg): ");
scanf("%f", &W);
sortByRatio(items, n);
float totalValue = 0.0, totalWeight = 0.0;
printf("\nItems selected for transport:\n");
printf("%-15s %-10s %-10s %-10s %-10s\n", "Name", "Weight", "Value", "Taken(kg)", "TotalVal");
for (int i = 0; i < n; i++) {
if (totalWeight + items[i].weight <= W) {
// Take whole item
totalWeight += items[i].weight;
totalValue += items[i].value;
printf("%-15s %-10.2f %-10.2f %-10.2f %-10.2f\n",
items[i].name, items[i].weight, items[i].value, items[i].weight, items[i].value);
} else {
// Take fraction if divisible
if (items[i].divisible) {
float remain = W - totalWeight;
float fractionValue = items[i].ratio * remain;
totalWeight += remain;
totalValue += fractionValue;
printf("%-15s %-10.2f %-10.2f %-10.2f %-10.2f\n",
items[i].name, items[i].weight, items[i].value, remain, fractionValue);
}
break; // Can't take any more items
}
}
printf("\nTotal weight carried: %.2f kg\n", totalWeight);
printf("Total utility value: %.2f\n", totalValue);
return 0;
}
Input:
Enter number of relief items: 4
Enter name of item 1: Medicine
Enter weight (kg): 10
Enter utility value: 60
Is the item divisible? (1 = Yes, 0 = No): 0
Enter name of item 2: Food
Enter weight (kg): 20
Enter utility value: 100
Is the item divisible? (1 = Yes, 0 = No): 1
Enter name of item 3: Water
Enter weight (kg): 30
Enter utility value: 120
Is the item divisible? (1 = Yes, 0 = No): 1
Enter name of item 4: Blanket
Enter weight (kg): 15
Enter utility value: 50
Is the item divisible? (1 = Yes, 0 = No): 0
Enter maximum weight capacity of the boat (kg): 50
Output:
Items selected for transport:
Name Weight Value Taken(kg) TotalVal
Medicine 10.00 60.00 10.00 60.00
Food 20.00 100.00 20.00 100.00
Water 30.00 120.00 20.00 80.00
Total weight carried: 50.00 kg
Total utility value: 240.00