Fractional Knapsack Lecture Notes

Problem Statement

• Given n items, each with a value and weight.
• Given a maximum weight W that a bag can carry.
• Task: Pick items in such a way to maximize the total value without exceeding W.
• Fractional knapsack: Items can be divided into fractions.

Example Walkthrough

1. Initial example: Items (value, weight)

   • (100, 20)
   • (60, 10)
   • (200, 50)
   • Bag Weight W = 90

2. Process:

   • Pick (100, 20): Weight left: 70
   • Pick (60, 10): Weight left: 60
   • Pick (200, 50): Weight left: 10
   • For (200, 50), only pick a fraction because the bag only has 10 weight left.
     • Fraction value: 200/50 = 4 per weight, so 10 weight gives 4*10 = 40

3. Total Value:

   • 100 + 60 + 100 + 40 = 300

Strategy to Maximize Value

• Greedily pick items based on value per unit weight.
• Calculate value per weight for each item.
  • Example: (Value, Weight)
    • (100, 20) => 5
    • (60, 10) => 6
    • (200, 50) => 4

Efficient Solution Strategy

1. Sort Items by Value per Weight:
   • Example Sorted: (60, 10), (100, 20), (200, 50)
2. Pick Items in Sorted Order:
   • Example process revisited:
     • Pick (60, 10): Weight left: 80
     • Pick (100, 20): Weight left: 60
     • Pick (200, 50): Weight left: 10
     • Pick fraction of (100, 50): 10 weight => Value 40
     • Total Value: 360

Pseudo Code

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

def fractional_knapsack(items, W):
    items.sort(key=lambda x: x.value/x.weight, reverse=True)
    total_value = 0.0
    for item in items:
        if item.weight <= W:
            W -= item.weight
            total_value += item.value
        else:
            total_value += item.value * (W / item.weight)
            break
    return total_value

1. Comparator to Sort Items:

   • Based on value/weight in descending order.

2. Iterate Through Sorted Items:

   • Pick entire items until weight limit is breached.
   • Pick fraction of remaining items based on remaining weight.

Key Takeaways

• Time Complexity: O(n log n) for sorting + O(n) for iteration.
• Space Complexity: O(1) as no extra space beyond input and a few variables.
• Approach is based on greedy algorithm to maximize value per unit weight.
• Ensure fractional values are handled using float or double types.

Final Words

• Greedy algorithms are powerful for optimization problems like this.
• Sorting items by a key metric is crucial to their success.
• Practice and understanding the concept of value per weight can provide deeper insights into similar problems.