concept · INFO-CS-ADS-185Fractional Knapsack Problem
Understand how a greedy algorithm maximizes the total value of a knapsack by selecting items according to their value-to-weight ratios, allowing fractions of items.
Explanation
Overview
The Fractional Knapsack Problem is an optimization problem in which items have individual weights and values, and a knapsack has a limited capacity. Unlike the 0/1 Knapsack Problem, an item can be divided, allowing only part of its weight and value to be selected.
Key concepts
Value-to-weight ratio; Greedy selection; Fractional item selection; Capacity constraint; Optimization; Greedy-choice property
Variables
weight[i]: The total weight of item i.; value[i]: The total value of item i.; capacity: The maximum weight the knapsack can hold.; ratio[i]: The value obtained per unit of weight for item i.; fraction[i]: The proportion of item i selected, between 0 and 1.
Complexity
sorting: O(n log n) time.; selection: O(n) time.; overall: O(n log n) time and O(1) auxiliary space if sorting is performed in place, excluding input storage.
Example
items: name: A; weight: 10; value: 60; name: B; weight: 20; value: 100; capacity: 50; selectedItems: name: A; selectedWeight: 10; selectedValue: 60; name: B; selectedWeight: 20; selectedValue: 100; totalWeight: 50; maximumValue: 240; explanation: Item A and item B are selected completely. The remaining capacity is 20, so two-thirds of item C is selected, providing an additional value of 80.
Pseudocode
function fractionalKnapsack(items, capacity):
sort items by value / weight in descending order
totalValue = 0
for item in items:
if capacity == 0:
break
selectedWeight = min(item.weight, capacity)
fraction = selectedWeight / item.weight
totalValue += fraction * item.value
capacity -= selectedWeight
return totalValue
Applications
Resource allocation.; Cargo loading when goods can be divided.; Budget distribution.; Material allocation.; Investment models with divisible quantities.
Variables
Weight[i]
The total weight of item i.
Value[i]
The total value of item i.
Capacity
The maximum weight the knapsack can hold.
Ratio[i]
The value obtained per unit of weight for item i.
Fraction[i]
The proportion of item i selected, between 0 and 1.
Example or application
Items
| Name | Weight | Value | Ratio |
|---|
A | 10 | 60 | 6 |
B | 20 | 100 | 5 |
C | 30 | 120 | 4 |
Selected Items
| Name | Selected Weight | Selected Value |
|---|
A | 10 | 60 |
B | 20 | 100 |
C | 20 | 80 |
Explanation
Item A and item B are selected completely. The remaining capacity is 20, so two-thirds of item C is selected, providing an additional value of 80.
Definition
The Fractional Knapsack Problem is an optimization problem in which items have individual weights and values, and a knapsack has a limited capacity. Unlike the 0/1 Knapsack Problem, an item can be divided, allowing only part of its weight and value to be selected.
Mathematical Representation
valueToWeightRatio[i] = value[i] / weight[i]. Select available items in descending order of this ratio until the capacity is filled.
Greedy Strategy
Calculate the value-to-weight ratio of every item.
Sort items in descending order of their ratios.
Select the highest-ratio item completely if it fits.
Continue selecting complete items while capacity remains.
If the next item does not fit completely, take only the fraction that fills the remaining capacity.
Stop when the knapsack is full or all items have been considered.
Pseudocode
function fractionalKnapsack(items, capacity):
sort items by value / weight in descending order
totalValue = 0
for item in items:
if capacity == 0:
break
selectedWeight = min(item.weight, capacity)
fraction = selectedWeight / item.weight
totalValue += fraction * item.value
capacity -= selectedWeight
return totalValue
Complexity
Overall
O(n log n) time and O(1) auxiliary space if sorting is performed in place, excluding input storage.
Advantages
Produces an optimal solution for the standard fractional knapsack problem.
Uses a straightforward sorting-based strategy.
Is efficient for large collections of items.
Allows partial selection when an item cannot fit completely.
Limitations
The greedy ratio strategy is not generally optimal for 0/1 Knapsack.
The standard model assumes items can be divided proportionally.
Indivisible or restricted resources require other optimization techniques.
Items with zero weight require special handling in the mathematical model.
Practice Question
An item weighs 10 kg and has a value of 80. What is its value-to-weight ratio?
Practice Answer
8 value units per kilogram.
Learning Objectives
Explain the central idea and purpose of fractional knapsack problem.
Identify the assumptions, inputs, and conditions relevant to fractional knapsack problem.
Evaluate an application of fractional knapsack problem for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Greedy Algorithms and Optimization
Suggest a correction or source · More in Algorithms & Data Structures