Fractional Knapsack Problem

The Fractional Knapsack Problem is a variant of the knapsack problem where it's permissible to take fractional parts of items rather than having to make a binary choice for each item (all or nothing). This problem allows for a greedy approach to find an optimal solution.

Problem Statement

Given a set of items, each with a weight and a value, and a knapsack with a limited capacity, the goal is to determine the maximum value that can be attained by selecting fractions of these items. The value of the fraction of an item chosen is directly proportional to its weight.

Greedy Strategy Determination

To solve the problem, the strategy involves:

1. Unit Value Calculation: Compute the value per unit weight for each item.
2. Sorting: Arrange the items based on their unit value in descending order.
3. Selection: Iteratively choose items based on their unit value. If the remaining capacity allows, add the entire item to the knapsack; otherwise, add as much of the item as possible to fill the knapsack.

This approach ensures that at every step, the most valuable fraction of an item relative to its weight is considered, maximizing the total value accumulated.

function fractionalKnapsack(capacity, items):
    // items is a list of tuples (value, weight)
    // Sort items by value-to-weight ratio in descending order
    items.sort(key=lambda item: item.value / item.weight, reverse=True)
    
    totalValue = 0
    for item in items:
        if capacity > 0 and item.weight <= capacity:
            // Take the whole item
            totalValue += item.value
            capacity -= item.weight
        else:
            // Take only the fraction of the item that fits
            totalValue += item.value * (capacity / item.weight)
            break
    return totalValue

Complexity

• Time Complexity: $O (n \log n)$ primarily due to the sort operation.
• Space Complexity: $O (n)$ for storing the item objects.

Implementation

Here's a Python implementation of the fractional knapsack using a greedy algorithm:

class Item:
    def __init__(self, w, v):
        self.w = w  # Item weight
        self.v = v  # Item value

def fractional_knapsack(wgt, val, cap):
    items = [Item(w, v) for w, v in zip(wgt, val)]
    # Sort items by their unit value in descending order
    items.sort(key=lambda item: item.v / item.w, reverse=True)
    res = 0
    for item in items:
        if item.w <= cap:
            res += item.v
            cap -= item.w
        else:
            res += (item.v / item.w) * cap
            break
    return res

Example

Suppose we have the following items and a knapsack with a capacity of 50 units:

• Item 1: Value = 60, Weight = 10
• Item 2: Value = 100, Weight = 20
• Item 3: Value = 120, Weight = 30

Sorting items by value-to-weight ratio gives:

• Item 2: Value-to-Weight = 5
• Item 3: Value-to-Weight = 4
• Item 1: Value-to-Weight = 6

Following the greedy strategy, we would:

1. Take all of Item 1 (10 units, adds 60 to value).
2. Take all of Item 2 (20 units, adds 100 to value).
3. Take 20 units of Item 3 (adds 80 to value).

This results in a total value of 240.

Correctness Proof

The correctness of the greedy strategy can be validated using a proof by contradiction:

Assume an item with the highest unit value is not included in the optimal set. Replacing a unit weight of any other item with this one will increase the total value, contradicting the assumption of optimality. Therefore, including items with higher unit values whenever possible ensures an optimal solution.