Greedy Technique to Solve the Fractional Knapsack Problem
To demonstrate solving a Knapsack Problem using a greedy algorithm, let's consider the Fractional Knapsack Problem. In this version, unlike the 0/1 Knapsack Problem, items can be divided into smaller parts. Here's an example:
Knapsack Problem Example:
- Items:
1. Item A: Weight =
10 kg, Value = $60
2. Item B: Weight =
20 kg, Value = $100
3. Item C: Weight =
30 kg, Value = $120
Step-by-Step Solution Using Greedy Algorithm:
1. Calculate Value-to-Weight Ratio for Each Item:
- Item A: $60/10 kg
= $6/kg
- Item B: $100/20
kg = $5/kg
- Item C: $120/30
kg = $4/kg
2. Sort Items by Their Value-to-Weight Ratio:
- Order: Item A ($6/kg), Item B ($5/kg), Item C ($4/kg)
3. Add Items to the Knapsack in the Order of Ratio, Until the Knapsack is Full or Items are Exhausted:
- Add Item A (10
kg): Remaining capacity = 50 kg - 10 kg = 40 kg, Total value = $60.
- Add Item B (20
kg): Remaining capacity = 40 kg - 20 kg = 20 kg, Total value = $60 + $100 =
$160.
- Add Item C: The
remaining capacity is 20 kg, but Item C is 30 kg. Since we can take fractions
of items, we take 20/30 of Item C.
- Value of 20/30 of Item C = (20/30) * $120 = $80.
4. Total Value in the Knapsack:
- Total value = $160 (from Items A and B) + $80 (from 20/30 of Item C) = $240.
Why the Solution is Greedy:
1. Prioritize Items by Value-to-Weight Ratio:
- First, calculate the value-to-weight ratio for each item.
- Item A: $6/kg, Item B: $5/kg, Item C: $4/kg.
2. Optimal Choice at Each Step:
- The greedy algorithm always picks the item with the highest value-to-weight ratio that the knapsack can still accommodate. This is the "greedy" choice – taking the best option available at the moment without considering future consequences.
3. Maximize Value with Current Information:
- The algorithm doesn't look ahead or consider the remaining items when making a choice. It simply picks the best item at each step. For example, it picks all of Item A first, then Item B, and as much of Item C as can fit.
4. Local Optimum Leading to Global Optimum:
- In the case of the Fractional Knapsack Problem, this greedy approach actually leads to the global optimum. The algorithm maximizes the total value in the knapsack at each step by choosing the best available item, and in this context, the best choices at each step also result in the best overall solution.
Conclusion:
Using the greedy approach, the optimal solution for this
Fractional Knapsack Problem is to take all of Item A, all of Item B, and 2/3 of
Item C, achieving a total value of $240.
C Program
#include <stdio.h>
#include <stdlib.h>
// Structure to represent an item in the knapsack
typedef struct {
int value;
int weight;
} Item;
// Comparator function to sort items based on value-to-weight ratio
int compare(const void *a, const void *b) {
Item *item1 = (Item *)a;
Item *item2 = (Item *)b;
double r1 = (double)item1->value / item1->weight;
double r2 = (double)item2->value / item2->weight;
return r2 - r1;
}
// Function to solve the Fractional Knapsack Problem using Greedy Method
double fractionalKnapsack(int W, Item arr[], int n) {
// Sorting items based on value-to-weight ratio
qsort(arr, n, sizeof(Item), compare);
int currentWeight = 0; // Current weight in knapsack
double finalValue = 0.0; // Result (value in Knapsack)
// Looping through all items
for (int i = 0; i < n; i++) {
// If adding item won't exceed the capacity, add it completely
if (currentWeight + arr[i].weight <= W) {
currentWeight += arr[i].weight;
finalValue += arr[i].value;
}
// Otherwise add the fractional part of it
else {
int remain = W - currentWeight;
finalValue += arr[i].value * ((double) remain / arr[i].weight);
break;
}
}
return finalValue;
}
int main() {
// Example items: each has a value and a weight
Item arr[] = {{60, 10}, {100, 20}, {120, 30}};
int W = 50; // Total weight capacity of knapsack
int n = sizeof(arr) / sizeof(arr[0]);
printf("Maximum value we can obtain = %.2f\n", fractionalKnapsack(W, arr, n));
return 0;
}
Comments
Post a Comment