3. write a program to perform knapsack problem using greedy solution. || DAA

#include <stdio.h>

typedef struct  

{ int weight; int value;

double valuePerWeight; // Value-to-Weight ratio

} Item;

int fractionalKnapsack(Item items[], int n, int capacity) {

// Calculate the value-to-weight ratio for each item  

for (int i = 0; i < n; i++) {

items[i].valuePerWeight = (double) items[i].value / items[i].weight;

}

// Sort items based on value-to-weight ratio (descending order)

for (int i = 0; i < n - 1; i++) {

for (int j = 0; j < n - i - 1; j++) {

if (items[ j ].valuePerWeight < items[j + 1].valuePerWeight) {

// Swap

Item temp = items[j];  

items[j] = items[j + 1];  

items[j + 1] = temp;

}

}

}

double totalValue = 0.0;

// Fill the knapsack

for (int i = 0; i < n && capacity > 0; i++) {

    if (items[i].weight <= capacity) {

// Take the whole item  

totalValue += items[i].value;  

capacity -= items[i].weight;

} else {

// Take a fraction of the item

double fraction = (double) capacity / items[i].weight;

totalValue += fraction * items[i].value;

capacity = 0;

}

}

printf("Maximum value in the knapsack: %.2f\n", totalValue);

}

int main() {

int n, capacity;

printf("Enter the number of items: ");

scanf("%d", &n);  

Item items[n];

printf("Enter the weight and value for each item:\n");

for (int i = 0; i < n; i++)  

{  

printf("Item %d:\n", i + 1);

printf("Weight: ");

scanf("%d", &items[i].weight);

printf("Value: ");

scanf("%d", &items[i].value);

}

printf("Enter the knapsack capacity: ");

scanf("%d", &capacity);

fractionalKnapsack(items, n, capacity);

return 0;

}