Fractional Knapsack Problem: Greedy Approach
Ever before picturise a backpacker who is planning to go on a trek. It’s a finite-capacity knapsack and choices are available with each item having a value and a weight. The problem is to fill the knapsack, monitoring a total value that does not surpass the provided weight capacity. And that is where The Fractional Knapsack Problem comes in where one can take fractions of the item without it being an either/or situation.
Problem Statement
The Fractional Knapsack Problem involves:
- A set of
n
items, where each item has: - Value (
v
): It's worth it. - Weight (
w
): Its mass or size.
2. A knapsack with a fixed capacity (W
) that cannot be exceeded.
Nonetheless, the aim is to find the best solution such that one has to, in this case, select items that will amount to the maximum total value that can possibly fit into the knapsack without crossing the set weight. Part of items may be taken and this moves it away from the 0/1 Knapsack Problem which only allows whole items to be taken.
Core Concepts
- Value-to-Weight Ratio (
v/w
): This ratio assists in establishing the efficiency of each item being compared or being in a relationship with another. Higher ratios signify those products which can provide more value for the weight. - Greedy Choice: This means that in fulfilling the above objectives, the top priority should be goods that have high value relative to the amount of weight they occupy.
Example Problem
Suppose we have three items:
- Item 1: Value = 60, Weight = 10
- Item 2: Value = 100, Weight = 20
- Item 3: Value = 120, Weight = 30
Knapsack capacity = 50.
Using the greedy approach, we calculate the value-to-weight ratios:
- Item 1: 6
- Item 2: 5
- Item 3: 4
We start by filling the knapsack with the highest ratio item, proceeding until the capacity is exhausted.
The Greedy Approach
The greedy algorithm is a step-by-step method that works as follows:
Steps
- Calculate Ratios: Rank each of the items according to the value-to-weight ratio.
- Sort Items: Rank rates from high to low.
- Pick Items: Continuously feed items into the knapsack, always using whole items when total volume allows it but using only a portion of items when it does not.
- Stop: When the knapsack reaches its capacity, terminate the process.
Implementation
Python
Here’s the Python implementation of the greedy approach for the Fractional Knapsack Problem:
def fractional_knapsack(values, weights, capacity):
n = len(values)
items = [(values[i], weights[i], values[i] / weights[i]) for i in range(n)]
items.sort(key=lambda x: x[2], reverse=True) # Sort by value-to-weight ratio
total_value = 0
for value, weight, ratio in items:
if capacity >= weight:
capacity -= weight
total_value += value
else:
total_value += ratio * capacity
break
return total_value
# Example usage
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
result = fractional_knapsack(values, weights, capacity)
print(f"Maximum value in knapsack: {result}")
Output:Maximum value in knapsack: 240.0
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structure to represent an item with value, weight, and value-to-weight ratio
struct Item {
double value;
double weight;
double ratio;
};
// Comparison function to sort items by value-to-weight ratio in descending order
bool compare(Item a, Item b) {
return a.ratio > b.ratio;
}
double fractionalKnapsack(vector<double> values, vector<double> weights, double capacity) {
int n = values.size();
vector<Item> items(n);
// Calculate value-to-weight ratio for each item
for (int i = 0; i < n; i++) {
items[i] = {values[i], weights[i], values[i] / weights[i]};
}
// Sort items by ratio in descending order
sort(items.begin(), items.end(), compare);
double totalValue = 0.0;
// Select items for the knapsack
for (int i = 0; i < n; i++) {
if (capacity >= items[i].weight) {
// Take the entire item
capacity -= items[i].weight;
totalValue += items[i].value;
} else {
// Take the fractional part of the item
totalValue += items[i].ratio * capacity;
break;
}
}
return totalValue;
}
int main() {
vector<double> values = {60, 100, 120};
vector<double> weights = {10, 20, 30};
double capacity = 50;
double result = fractionalKnapsack(values, weights, capacity);
cout << "Maximum value in knapsack: " << result << endl;
return 0;
}
Input:
values = {60, 100, 120}
weights = {10, 20, 30}
capacity = 50
Output:Maximum value in knapsack: 240
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
class Item {
double value;
double weight;
double ratio;
public Item(double value, double weight) {
this.value = value;
this.weight = weight;
this.ratio = value / weight;
}
}
public class FractionalKnapsack {
public static double fractionalKnapsack(double[] values, double[] weights, double capacity) {
int n = values.length;
List<Item> items = new ArrayList<>();
// Create a list of items with value, weight, and ratio
for (int i = 0; i < n; i++) {
items.add(new Item(values[i], weights[i]));
}
// Sort items by value-to-weight ratio in descending order
Collections.sort(items, new Comparator<Item>() {
@Override
public int compare(Item o1, Item o2) {
return Double.compare(o2.ratio, o1.ratio);
}
});
double totalValue = 0.0;
// Select items for the knapsack
for (Item item : items) {
if (capacity >= item.weight) {
// Take the entire item
capacity -= item.weight;
totalValue += item.value;
} else {
// Take a fractional part of the item
totalValue += item.ratio * capacity;
break;
}
}
return totalValue;
}
public static void main(String[] args) {
double[] values = {60, 100, 120};
double[] weights = {10, 20, 30};
double capacity = 50;
double result = fractionalKnapsack(values, weights, capacity);
System.out.println("Maximum value in knapsack: " + result);
}
}
Input:
values = {60, 100, 120}
weights = {10, 20, 30}
capacity = 50
Output:Maximum value in knapsack: 240
Time Complexity
- Sorting: O(nlogn)
- Selection: O(n)
Thus, the overall time complexity is O(nlogn)
Real-World Applications
The Fractional Knapsack Problem has wide applicability, including:
1. Shipping & Freight Optimization
Logistics companies typically ship goods either underweight or under volume constraints. Using the Fractional Knapsack approach they can prioritize their high-value items to maximize profit.
2. Resource Allocation in IT
In the cloud context, the allocation of limited resources (e.g., CPU time, bandwidth, or storage) must be optimized for maximum utility within limited budgets.
3. In Times of Disaster and Humanitarian Need
Transportation resources are scarce in disaster situations. Such calculation of value-to-weight efficiency is also utilized by relief organizations to prioritize supplies (including food and medicine).
4. Financial Portfolio Management
After that, investors invest money in an asset (stocks, bonds, mutual funds, etc.) to maximize returns. This ensures we index the proportion in which each asset would need to be allocated using the Fractional Knapsack analogy.
5. E-Commerce Inventory and Storage
Under space constraints in the warehouse, e-commerce companies manage the inventory. Profitability comes from putting the most valuable things in the smallest amount of space.
Comparison of Fractional Knapsack to 0/1 Knapsack
Aspect | Fractional Knapsack | 0/1 Knapsack |
---|---|---|
Item Selection | Fractions allowed | Whole items only |
Solution Approach | Greedy algorithm | Dynamic programming or backtracking |
Complexity | O(n log n) | O(n × W) |
Conclusion
The Fractional Knapsack Problem showcases the power of mathematical optimization to tackle practical challenges effectively. It makes decision-making easier in resource-limited situations through the greedy algorithm — department services.
The Fractional Knapsack Problem, whether in cases of logistics financial planning or disaster relief, can provide great insights when it comes to prioritization and the allocation of resources. Its elegant simplicity showcases how we can leverage algorithmic thinking to solve everyday problems is one of the reasons it is a story as old as time — literally since we learned programming algorithms — despite being one of the most "timeless" computer science topics.