Fractional Knapsack Problem in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fractional Knapsack Value Calculation

What is the output of the following Python code that calculates the maximum value for the fractional knapsack problem?

DSA Python

def fractional_knapsack(values, weights, capacity):
    index = list(range(len(values)))
    ratio = [v/w for v, w in zip(values, weights)]
    index.sort(key=lambda i: ratio[i], reverse=True)
    max_value = 0
    for i in index:
        if weights[i] <= capacity:
            max_value += values[i]
            capacity -= weights[i]
        else:
            max_value += ratio[i] * capacity
            break
    return round(max_value, 2)

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(fractional_knapsack(values, weights, capacity))

A 240.0

B 220.0

C 180.0

D 200.0

💡 Hint

Think about sorting items by value-to-weight ratio and taking fractions if needed.

The function sorts items by value/weight ratio: 60/10=6, 100/20=5, 120/30=4. Sorted order is item with ratio 6, then 5, then 4. It takes full items 1 and 2, then fraction of item 3 to fill capacity 50. Total value is 60 + 100 + (4 * 20) = 240.

🧠 Conceptual

intermediate

Key Idea Behind Fractional Knapsack

Which of the following best describes the main idea behind the fractional knapsack problem?

A Take items with the highest value first, ignoring weight.

B Take items with the lowest weight first to maximize quantity.

C Take items with the highest value-to-weight ratio first, possibly taking fractions of items.

D Take items randomly until capacity is full.

💡 Hint

Think about how to maximize value per unit weight.

The fractional knapsack problem is solved by taking items with the highest value-to-weight ratio first, allowing fractions of items to fill the knapsack optimally.

🔧 Debug

advanced

Identify the Error in Fractional Knapsack Implementation

What error will the following code produce when executed?

DSA Python

def fractional_knapsack(values, weights, capacity):
    ratio = [v/w for v, w in zip(values, weights)]
    index = sorted(range(len(values)), key=lambda i: ratio[i])
    max_value = 0
    for i in index:
        if weights[i] <= capacity:
            max_value += values[i]
            capacity -= weights[i]
        else:
            max_value += ratio[i] * capacity
            break
    return max_value

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(fractional_knapsack(values, weights, capacity))

A The output is 240.0

B The output is 220.0

C The output is 140.0

D The output is 180.0

💡 Hint

Check the sorting order of the ratio list.

The code sorts the items by ratio in ascending order, so it takes the lowest value-to-weight ratio items first, which is incorrect for maximizing value. It results in a total value of 220.

❓ Predict Output

advanced

Output of Fractional Knapsack with Zero Capacity

What is the output of this code when the knapsack capacity is zero?

DSA Python

def fractional_knapsack(values, weights, capacity):
    ratio = [v/w for v, w in zip(values, weights)]
    index = sorted(range(len(values)), key=lambda i: ratio[i], reverse=True)
    max_value = 0
    for i in index:
        if weights[i] <= capacity:
            max_value += values[i]
            capacity -= weights[i]
        else:
            max_value += ratio[i] * capacity
            break
    return max_value

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 0
print(fractional_knapsack(values, weights, capacity))

A 0

B 60

C 120

D None

💡 Hint

If capacity is zero, no items can be taken.

Since the capacity is zero, the knapsack cannot hold any items, so the total value is zero.

🚀 Application

expert

Maximum Value with Fractional Knapsack for Large Input

Given 4 items with values [500, 400, 300, 450] and weights [50, 40, 30, 45], and a knapsack capacity of 100, what is the maximum value the knapsack can hold?

A 950.0

B 975.0

C 1100.0

D 1000.0

💡 Hint

Calculate value-to-weight ratios and take items in descending order, possibly fractions.

All items have the same value-to-weight ratio of 10, so the maximum value is capacity * 10 = 1000.0.

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