Fractional Knapsack Problem in DSA Python - Execution Trace

Concept Flow - Fractional Knapsack Problem

Sort items by value/weight ratio

↓

Initialize total_weight=0, total_value=0

↓

For each item in sorted list

↓

Can full item fit?

No→Take fraction to fill knapsack

|Yes↓

Add full item value and weight

↓

Update total_weight and total_value

↓

Knapsack full?

No→Next item

|Yes↓

Done

The algorithm sorts items by value per weight, then adds full or fractional items until the knapsack is full.

Execution Sample

DSA Python

items = [(60, 10), (100, 20), (120, 30)]
capacity = 50
# Sort by value/weight
items.sort(key=lambda x: x[0]/x[1], reverse=True)
total_value = 0
current_weight = 0
for value, weight in items:
    if current_weight + weight <= capacity:
        total_value += value
        current_weight += weight
    else:
        remain = capacity - current_weight
        total_value += value * (remain / weight)
        break
print(total_value)

This code calculates the maximum value for a knapsack of capacity 50 using fractional items.

Execution Table

Step	Operation	Item (Value, Weight)	Current Weight	Added Weight	Added Value	Total Value	Knapsack State
1	Sort items by value/weight ratio	[(60,10), (100,20), (120,30)]	0	0	0	0	Empty
2	Take full item	(60,10)	0	10	60	60	10/50 filled
3	Take full item	(100,20)	10	20	100	160	30/50 filled
4	Take fraction of item	(120,30)	30	20	80	240	50/50 filled (fractional)
5	Done	-	50	0	0	240	Knapsack full

💡 Knapsack reached full capacity at step 4 by taking fraction of last item.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
total_value	0	60	160	240	240
current_weight	0	10	30	50	50
capacity	50	50	50	50	50

Key Moments - 3 Insights

Why do we sort items by value/weight ratio first?

Sorting ensures we pick items that give the most value per weight first, maximizing total value as shown in execution_table step 1.

Why do we take only a fraction of the last item?

When adding the full item exceeds capacity, we take only the needed fraction to fill the knapsack exactly, as seen in step 4.

What happens if the knapsack capacity is reached exactly after adding an item?

The loop stops immediately, no fraction needed, as the knapsack is full, similar to the check after step 3 if capacity was 30.

Visual Quiz - 3 Questions

Look at the execution_table, what is the total_value after step 3?

A 160

B 100

C 60

D 240

💡 Hint

Check the 'Total Value' column at step 3 in execution_table.

At which step does the knapsack become full?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Knapsack State' column to see when it reaches 50/50 filled.

If the capacity was 60 instead of 50, what would happen at step 4?

A Take full item (120,30)

B Take fraction of item (120,30)

C Skip item (120,30)

D Stop before step 4

💡 Hint

Check variable_tracker for current_weight after step 3 and compare with new capacity.

Concept Snapshot

Fractional Knapsack Problem:
- Sort items by value/weight ratio descending
- Add full items while capacity allows
- Add fraction of next item if needed
- Maximizes total value with fractional items
- Greedy approach, O(n log n) due to sorting

Full Transcript

The Fractional Knapsack Problem finds the maximum value that fits in a knapsack with limited capacity by allowing fractions of items. First, items are sorted by their value-to-weight ratio. Then, starting from the highest ratio, full items are added until the knapsack cannot fit the next full item. At that point, only the fraction of the item that fits is added. This process continues until the knapsack is full. The example code sorts items, iterates through them, and adds full or fractional parts accordingly. The execution table shows each step's operation, current weight, added weight and value, and the knapsack's fill state. Key moments clarify why sorting is essential, why fractions are taken, and what happens when capacity is exactly reached. The visual quiz tests understanding of total value at steps, when the knapsack fills, and how capacity changes affect the process.

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