Fractional knapsack problem in C
In this article, we will discuss the fractional knapsack problem in C with its example.
Question:
You are given a set of n items, each with a specific value and weight. The goal is to maximize the total value that can be put into a knapsack with a weight capacity of capacity. The items can be taken in fractional parts. Write a C program to find the maximum value that can be achieved using the Fractional Knapsack Algorithm.
Constraints:
The number of items n (1 ≤ n ≤ 1000).
The weight capacity of the knapsack capacity (1 ≤ capacity ≤ 1000).
The value and weight of each item (1 ≤ value, weight ≤ 100).
Example:
Let's take an example to demonstrate the fractional knapsack problem in C.
Code:
#include <stdio.h>
#include <stdlib.h>
// Structure to represent an item
struct Item {
int value;
int weight;
};
// Function to compare items by their value per unit weight
int compareItems(const void* a, const void* b) {
struct Item* itemA = (struct Item*)a;
struct Item* itemB = (struct Item*)b;
double ratioA = (double)itemA->value / itemA->weight;
double ratioB = (double)itemB->value / itemB->weight;
if (ratioA>ratioB)
return -1;
else if (ratioA<ratioB)
return 1;
return 0;
}
double fractionalKnapsack(struct Item items[], int n, int capacity) {
// Sort items based on their value per unit weight
qsort(items, n, sizeof(struct Item), compareItems);
double totalValue = 0.0;
int currentWeight = 0;
for (int i = 0; i< n; i++) {
if (currentWeight + items[i].weight<= capacity) {
// If the whole item can be taken, take it
currentWeight += items[i].weight;
totalValue += items[i].value;
} else {
// Take a fractional part of the item
int remainingCapacity = capacity - currentWeight;
totalValue += (double)items[i].value / items[i].weight * remainingCapacity;
break;
}
}
return totalValue;
}
int main() {
int capacity = 50;
struct Item items[] = { {60, 10}, {100, 20}, {120, 30} };
int n = sizeof(items) / sizeof(items[0]);
double maxValue = fractionalKnapsack(items, n, capacity);
printf("Maximum value in the knapsack: %.2lf\n", maxValue);
return 0;
}
Output:
![Fractional knapsack problem in C](https://static.tutorialandexample.com/c/fractional-knapsack-problem-in-c1.png)
Explanation:
In this example, we take various functions. Let's discuss these functions one by one:
struct Item: It is a structure used to represent each item. Each item has two properties: value (representing the value of the item) and weight (representing the weight of the item).
compareItems(const void* a, const void* b): It is a comparison function used to sort the items based on their value per unit weight in descending order. The function takes two pointers to struct Item as input (a and b) and compares them based on their value-to-weight ratios.
fractionalKnapsack(struct Item items[], int n, int capacity): It is the main function that solves the Fractional Knapsack Problem. It takes three arguments:
items: An array of struct Item representing the items available.
n: An integer representing the number of items in the array.
capacity: An integer representing the weight capacity of the knapsack.
The function returns a double value, which represents the maximum value that can be put into the knapsack with the given capacity.
Inside fractionalKnapsack:
First, the function sorts the items array based on their value per unit weight in descending order using qsort and the compareItems function. After that, it initializes totalValue to 0.0 and currentWeight to 0, representing the total value of items taken so far and the current weight in the knapsack, respectively.
The function iterates over the sorted items in the items array:
If the current item's weight can be accommodated in the knapsack without exceeding the capacity, the whole item is taken, and its value is added to the totalValue. The currentWeight is updated accordingly.
If the item's weight cannot be fully taken due to capacity constraints, a fractional part of the item is taken so that the knapsack becomes full. The value of the fractional part is calculated based on the remaining capacity in the knapsack.
main(): It is the entry point of the program. Inside the main function:
An array of struct Item called items is created, representing the available items with their respective values and weights.
The n variable is set to the number of items in the array (sizeof(items) / sizeof(items[0])).
The capacity variable is set to the weight capacity of the knapsack (e.g., 50).
The fractionalKnapsack function is called with the items array, n, and capacity as arguments and the result is stored in maxValue.
Finally, the maximum value that can be put in the knapsack is printed as output.
Conclusion:
The program uses the Fractional Knapsack algorithm to efficiently fill the knapsack with items that have the highest value-to-weight ratio, ensuring the knapsack is optimally filled without exceeding its weight limit. The maximum value that can be put in the knapsack is then printed as output.