Fractional Knapsack (Greedy Algorithm)
Maximize profit by taking fractions of items using greedy approach based on value-to-weight ratio
Fractional Knapsack Problem (Greedy Algorithm)
The Fractional Knapsack problem allows taking fractions of items to maximize profit. The greedy approach sorts items by value-to-weight ratio and takes items greedily.
Theory & Concepts
Definition:
Given items with weights and values, and a knapsack with capacity W, select items (or fractions) to maximize total value while staying within weight capacity.
Key Points:
- Greedy choice: select item with highest value-to-weight ratio first
- Items can be taken in fractions unlike 0/1 knapsack
- Always produces optimal solution for fractional variant
- Time complexity: O(n log n) due to sorting
Applications:
- Resource allocation with divisible resources
- Investment portfolio optimization
- Network bandwidth allocation
- Continuous optimization problems
University Guidelines
Exam Weightage
8-12 marks MarksSyllabus Coverage:
- Greedy Algorithm Strategy
- Fractional Knapsack Problem
- Value-to-Weight Ratio Analysis
- Greedy Choice Property
- Optimal Substructure Property
Common Questions:
- Solve fractional knapsack using greedy approach
- Compare with 0/1 knapsack solution
- Prove why greedy works for fractional variant
- Trace algorithm execution step by step
Exam Tips:
Always sort items by value/weight ratio in descending order
Show the calculation of ratios clearly
Take items completely until capacity allows, then take fraction
Calculate total profit step by step
Algorithm Details
O(n log n) for sorting + O(n) for selection
Time Complexity
O(1) auxiliary space
Space Complexity
Algorithm Steps:
- 1Calculate value-to-weight ratio for each item
- 2Sort items in descending order of ratio
- 3Initialize total value = 0, remaining capacity = W
- 4For each item, take maximum possible (whole or fraction)
- 5Update total value and remaining capacity
- 6Continue until capacity is exhausted
Problem Input
Items:
Item 1:
Ratio: --
Algorithm Overview
Greedy Strategy:
- Calculate value-to-weight ratio for each item
- Sort items by ratio in descending order
- Greedily select items with highest ratios first
- Take fractions of items when capacity is partially available
Why Greedy Works:
- Greedy choice property: local optimal choice leads to global optimum
- Optimal substructure: optimal solution contains optimal sub-solutions
- Exchange argument proves optimality for fractional variant
- Time: O(n log n), Space: O(1) - very efficient