Fractional Knapsack Problem in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Fractional Knapsack Problem?

To maximize the total value of items placed in a knapsack without exceeding its weight capacity, allowing fractions of items to be taken.

beginner

Why can we take fractions of items in the Fractional Knapsack Problem but not in the 0/1 Knapsack Problem?

Because the problem assumes items are divisible, so we can take any portion of an item, unlike 0/1 Knapsack where items are indivisible and must be taken whole or not at all.

intermediate

What is the greedy strategy used in the Fractional Knapsack Problem?

Sort items by their value-to-weight ratio in descending order and take as much as possible from the highest ratio items first.

intermediate

Explain the time complexity of the Fractional Knapsack Problem solution using the greedy approach.

The time complexity is O(n log n) due to sorting the items by their value-to-weight ratio, where n is the number of items.

beginner

In the Fractional Knapsack Problem, what happens if the knapsack capacity is reached while taking a fraction of an item?

We take only the fraction of the item that fits exactly into the remaining capacity, then stop as the knapsack is full.

What is the key difference between the Fractional Knapsack and 0/1 Knapsack problems?

A Both allow fractions of items.

B 0/1 Knapsack allows fractions, Fractional Knapsack does not.

C Fractional Knapsack allows taking parts of items, 0/1 Knapsack does not.

D Neither allows fractions of items.

Fractional Knapsack allows taking any fraction of an item, while 0/1 Knapsack requires taking the whole item or none.

Which greedy criterion is used to select items in the Fractional Knapsack Problem?

A Highest value-to-weight ratio first

B Lowest value first

C Highest weight first

D Random selection

Items are chosen based on the highest value-to-weight ratio to maximize total value.

What is the time complexity of the Fractional Knapsack algorithm using sorting?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

Sorting the items by value-to-weight ratio takes O(n log n) time.

If the knapsack capacity is 50 and the next item weighs 30, but only 20 capacity is left, what do we do?

A Skip the item

B Take half the item

C Take the whole item

D Take a fraction of the item weighing 20

We take only the fraction of the item that fits the remaining capacity, which is 20 units.

Which of these is NOT true about the Fractional Knapsack Problem?

A Items must be taken whole or not at all.

B It allows partial items to maximize value.

C It can be solved optimally using a greedy approach.

D Sorting items by value-to-weight ratio is essential.

Fractional Knapsack allows taking parts of items, so items do not have to be taken whole.

Describe the steps to solve the Fractional Knapsack Problem using a greedy approach.

Think about how to pick items to get the most value per weight.

Explain why the greedy method works optimally for the Fractional Knapsack Problem but not for the 0/1 Knapsack Problem.

Consider the difference in item divisibility.

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