Fractional Knapsack Problem: Greedy Approach

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:

  1. A set of n items, where each item has:
  2. Value (v): It's worth it.
  3. 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

  1. Calculate Ratios: Rank each of the items according to the value-to-weight ratio.
  2. Sort Items: Rank rates from high to low.
  3. 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.
  4. 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(nlog⁡n)
  • Selection: O(n)
    Thus, the overall time complexity is O(nlog⁡n)

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

Knapsack Comparison
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.