Fractional Knapsack Problem in DSA Python

Mental Model

We want to fill a bag with items to get the most value, and we can take parts of items if needed.

Analogy: Imagine filling a jar with different types of honey jars. You want the sweetest honey first, and if the jar is almost full, you take only part of the last honey jar to fill it perfectly.

Items: [weight: 10, value: 60] -> [weight: 20, value: 100] -> [weight: 30, value: 120]
Knapsack capacity: 50
Goal: maximize total value by taking whole or fractional parts of items.

Dry Run Walkthrough

Input: items: [(weight=10, value=60), (weight=20, value=100), (weight=30, value=120)], knapsack capacity=50

Goal: Maximize total value by selecting whole or fractional parts of items within capacity 50

Step 1: Calculate value per weight for each item and sort items by this ratio descending

Items sorted by value/weight: [(10,60,6.0), (20,100,5.0), (30,120,4.0)]

Why: We want to pick items with highest value per weight first to maximize total value

Step 2: Take whole first item (weight 10, value 60) into knapsack

Knapsack: 10/50 weight used, total value 60

Why: We can take whole item because it fits fully

Step 3: Take whole second item (weight 20, value 100) into knapsack

Knapsack: 30/50 weight used, total value 160

Why: Still have capacity, so take whole next best item

Step 4: Take fractional part of third item to fill remaining capacity (20/30 of item, value 80)

Knapsack: 50/50 weight used, total value 240

Why: Only partial weight left, so take fraction of item to maximize value

Result:

Knapsack full: total value = 240

Annotated Code

DSA Python

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

def fractional_knapsack(items, capacity):
    # Sort items by value per weight ratio descending
    items.sort(key=lambda x: x.ratio, reverse=True)
    total_value = 0.0
    remaining_capacity = capacity

    for item in items:
        if remaining_capacity == 0:
            break
        if item.weight <= remaining_capacity:
            # Take whole item
            total_value += item.value
            remaining_capacity -= item.weight
        else:
            # Take fractional part
            fraction = remaining_capacity / item.weight
            total_value += item.value * fraction
            remaining_capacity = 0
    return total_value

# Driver code
items = [Item(10, 60), Item(20, 100), Item(30, 120)]
capacity = 50
max_value = fractional_knapsack(items, capacity)
print(f"Maximum value in knapsack = {max_value}")

items.sort(key=lambda x: x.ratio, reverse=True)

Sort items by value per weight ratio descending to prioritize best value

for item in items:

Iterate over sorted items to pick them in order

if item.weight <= remaining_capacity:

Check if whole item fits in remaining capacity

total_value += item.value remaining_capacity -= item.weight

Add whole item value and reduce capacity accordingly

fraction = remaining_capacity / item.weight total_value += item.value * fraction remaining_capacity = 0

Take fractional part of item to fill knapsack exactly

Output

Maximum value in knapsack = 240.0

Complexity Analysis

Time: O(n log n) because we sort n items by value/weight ratio

Space: O(n) for storing items and their ratios

vs Alternative: Compared to 0/1 knapsack which is O(n*capacity), fractional knapsack is faster due to greedy sorting and no dynamic programming

Edge Cases

Empty list of items

Returns 0.0 as no items to take

DSA Python

for item in items:

Knapsack capacity zero

Returns 0.0 as no capacity to take any item

DSA Python

if remaining_capacity == 0:
    break

Items with zero weight (invalid)

Code will raise division by zero error; needs validation outside

DSA Python

items.sort(key=lambda x: x.ratio, reverse=True)

When to Use This Pattern

When you can take parts of items to maximize value under weight limit, use fractional knapsack greedy approach sorting by value/weight ratio.

Common Mistakes

Mistake: Not sorting items by value per weight ratio before selection
Fix: Sort items descending by value/weight ratio to ensure greedy picks maximize value

Mistake: Trying to take whole items only, ignoring fractional parts
Fix: Allow fractional part of last item to fill remaining capacity exactly

Summary

Find the maximum value by taking whole or fractional parts of items within capacity.

Use when items can be divided and you want to maximize value under weight limit.

Sort items by value per weight ratio and greedily take as much as possible from best ratio items.

Practice

1. What is the main goal of the Fractional Knapsack Problem?

easy

A. Maximize total value by taking fractions of items within weight limit

B. Minimize total weight by selecting whole items only

C. Maximize number of items regardless of weight

D. Select items randomly without considering value or weight

Solution

1. Step 1: Understand problem objective

   The fractional knapsack problem aims to maximize the total value of items taken, allowing fractions of items to fit within the weight limit.

2. Step 2: Compare options

   Only Maximize total value by taking fractions of items within weight limit correctly describes maximizing value with fractional items. Others describe incorrect goals.

3. Final Answer:

   Maximize total value by taking fractions of items within weight limit -> Option A

4. Quick Check:

   Goal = Maximize value with fractions [OK]

Hint: Remember: fractional means partial items allowed [OK]

Common Mistakes:

• Thinking only whole items can be taken
• Confusing value maximization with weight minimization
• Ignoring the fractional part of items

2. Which of the following Python code snippets correctly sorts items by value-to-weight ratio for the fractional knapsack?

easy

A. items.sort(key=lambda x: x[0]/x[1], reverse=True)

B. items.sort(key=lambda x: x[1]/x[0], reverse=True)

C. items.sort(key=lambda x: x[1]+x[0], reverse=True)

D. items.sort(key=lambda x: x[0]-x[1], reverse=True)

Solution

1. Step 1: Identify ratio for sorting

   Value-to-weight ratio is value divided by weight, so ratio = x[1]/x[0].

2. Step 2: Check sorting code

   items.sort(key=lambda x: x[1]/x[0], reverse=True) sorts items by this ratio descending, which is correct for fractional knapsack.

3. Final Answer:

   items.sort(key=lambda x: x[1]/x[0], reverse=True) -> Option B

4. Quick Check:

   Sort by value/weight descending [OK]

Hint: Sort by value divided by weight, descending [OK]

Common Mistakes:

• Reversing numerator and denominator
• Sorting by sum or difference instead of ratio
• Not using reverse=True for descending order

3. What is the output of this code snippet for fractional knapsack?

items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
items.sort(key=lambda x: x[1]/x[0], reverse=True)
total_value = 0
for w, v in items:
    if capacity >= w:
        capacity -= w
        total_value += v
    else:
        total_value += v * (capacity / w)
        break
print(round(total_value, 2))

medium

A. 240.00

B. 220.00

C. 180.00

D. 200.00

Solution

1. Step 1: Sort items by value/weight ratio

   Ratios: (60/10)=6, (100/20)=5, (120/30)=4. Sorted order: (10,60), (20,100), (30,120).

2. Step 2: Add items until capacity is full

   Take full 10 weight: value=60, capacity=40 left.
   Take full 20 weight: value=60+100=160, capacity=20 left.
   Take fraction of last item: fraction=20/30=2/3, value=160 + 120*(2/3)=160 + 80=240.
   But code prints rounded total_value after break, so total_value=240.

3. Final Answer:

   240.00 -> Option A

4. Quick Check:

   Sum values with fractions = 240.00 [OK]

Hint: Add full items first, then fraction of last item [OK]

Common Mistakes:

• Not sorting items by ratio
• Adding fractions incorrectly
• Rounding errors

4. Find the error in this fractional knapsack code snippet:

def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x[0]/x[1], reverse=True)
    total_value = 0
    for w, v in items:
        if capacity >= w:
            capacity -= w
            total_value += v
        else:
            total_value += v * (capacity / w)
            break
    return total_value

print(fractional_knapsack([(10, 60), (20, 100), (30, 120)], 50))

medium

A. Function returns total_value before loop

B. Loop variables w and v are swapped

C. Capacity is not updated after taking fraction

D. Sorting ratio is reversed; should be value/weight, not weight/value

Solution

1. Step 1: Check sorting key

   Sorting uses x[0]/x[1] which is weight/value, but ratio should be value/weight (x[1]/x[0]).

2. Step 2: Verify other parts

   Loop variables and capacity update are correct; function returns after loop.

3. Final Answer:

   Sorting ratio is reversed; should be value/weight, not weight/value -> Option D

4. Quick Check:

   Sort by value/weight, not weight/value [OK]

Hint: Sort by value divided by weight, not the other way [OK]

Common Mistakes:

• Using weight/value instead of value/weight for sorting
• Swapping weight and value in loop
• Not updating capacity after fraction

5. Given items with weights and values: [(5, 30), (10, 40), (15, 45)], and capacity 20, what is the maximum value achievable using fractional knapsack?

hard

A. 70.0

B. 75.0

C. 85.0

D. 80.0

Solution

1. Step 1: Calculate value/weight ratios and sort

   Ratios: (30/5)=6, (40/10)=4, (45/15)=3.
   Sorted order: (5,30), (10,40), (15,45).

2. Step 2: Add items until capacity full

   Take full 5 weight: value=30, capacity=15 left.
   Take full 10 weight: value=30+40=70, capacity=5 left.
   Take fraction of last item: fraction=5/15=1/3, value=70 + 45*(1/3)=70 + 15=85.

3. Final Answer:

   85.0 -> Option C

4. Quick Check:

   Sum values with fractions = 85.0 [OK]

Hint: Take full items by ratio, then fraction last to fill capacity [OK]

Common Mistakes:

• Not sorting by ratio
• Taking items in wrong order
• Calculating fraction incorrectly