✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-185

Fractional 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

NameWeightValueRatio

A

10

60

6

B

20

100

5

C

30

120

4

Capacity

50

Selected Items

NameSelected WeightSelected Value

A

10

60

B

20

100

C

20

80

Total Weight

50

Maximum Value

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.

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

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.

Key Concepts

  • Value-to-weight ratio

  • Greedy selection

  • Fractional item selection

  • Capacity constraint

  • Optimization

  • Greedy-choice property

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.

Applications

  • Resource allocation.

  • Cargo loading when goods can be divided.

  • Budget distribution.

  • Material allocation.

  • Investment models with divisible quantities.

Related Topics

  • 0/1 Knapsack Problem

  • Unbounded Knapsack Problem

  • Greedy Algorithms

  • Optimization Problems

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