Design and implement C/C++ Program to solve discrete Knapsack and continuous Knapsack problems using greedy approximation method.
#include <stdio.h>
#include <stdlib.h>
// Structure for an item
typedef struct {
int value;
int weight;
float ratio;
} Item;
// Comparator for sorting items by value-to-weight ratio
int compare(const void *a, const void *b) {
Item *item1 = (Item *)a;
Item *item2 = (Item *)b;
if (item2->ratio > item1->ratio) return 1;
else if (item2->ratio < item1->ratio) return -1;
else return 0;
}
// Function for 0/1 Knapsack (Greedy Approximation)
int greedyDiscreteKnapsack(Item items[], int n, int capacity) {
int totalValue = 0;
int i;
for (i = 0; i < n; i++) {
if (items[i].weight <= capacity) {
capacity -= items[i].weight;
totalValue += items[i].value;
}
}
return totalValue;
}
// Function for Fractional Knapsack (Greedy)
float greedyFractionalKnapsack(Item items[], int n, int capacity) {
float totalValue = 0.0;
int i;
for (i = 0; i < n; i++) {
if (capacity >= items[i].weight)
{
capacity -= items[i].weight;
totalValue += items[i].value;
}
else {
totalValue += items[i].ratio * capacity;
break;
}
}
return totalValue;
}
int main() {
int n, i, capacity;
// Input number of items
printf("Enter number of items: ");
scanf("%d", &n);
Item items[n];
// Input values and weights
for (i = 0; i < n; i++) {
printf("Enter value and weight of item %d: ", i + 1);
scanf("%d %d", &items[i].value, &items[i].weight);
items[i].ratio = (float)items[i].value / items[i].weight;
}
// Input capacity of knapsack
printf("Enter the capacity of the knapsack: ");
scanf("%d", &capacity);
// Sort items by ratio in descending order
qsort(items, n, sizeof(Item), compare);
// Call Greedy Discrete Knapsack
int discValue = greedyDiscreteKnapsack(items, n, capacity);
printf("Approximate value with Discrete Knapsack (0/1 Greedy) = %d\n", discValue);
// Call Fractional Knapsack
float fracValue = greedyFractionalKnapsack(items, n, capacity);
printf("Optimal value with Fractional Knapsack = %.2f\n", fracValue);
return 0;
}
OUTPUT:
Enter number of items: 4
Enter value and weight of item 1: 40 4
Enter value and weight of item 2: 42 7
Enter value and weight of item 3: 25 5
Enter value and weight of item 4: 12 3
Enter the capacity of the knapsack: 10
Approximate value with Discrete Knapsack (0/1 Greedy) = 65
Optimal value with Fractional Knapsack = 76.00