Fractional Knapsack Problem in DSA Python - Build from Scratch

Fractional Knapsack Problem

📖 Scenario: You are packing a bag for a hiking trip. You have several items, each with a weight and a value. Your bag can only carry a limited weight. You want to maximize the total value of items in your bag. You can take fractions of items if needed.

🎯 Goal: Build a program that calculates the maximum value you can carry in your bag using the fractional knapsack approach.

📋 What You'll Learn

Create a list of items where each item is a dictionary with keys 'value' and 'weight'.

Create a variable for the maximum weight the bag can carry.

Calculate the value-to-weight ratio for each item.

Sort the items by their value-to-weight ratio in descending order.

Select items or fractions of items to maximize total value without exceeding the bag's weight limit.

Print the maximum total value that can be carried.

💡 Why This Matters

🌍 Real World

This problem models packing or resource allocation where partial quantities can be taken, such as loading cargo or cutting materials.

💼 Career

Understanding fractional knapsack helps in optimization tasks, resource management, and algorithm design roles in software engineering.

1

Create the list of items

Create a list called items with these exact dictionaries: {'value': 60, 'weight': 10}, {'value': 100, 'weight': 20}, {'value': 120, 'weight': 30}

DSA Python

# Create the list of items with value and weight
# Your code here

Hint

Use a list with dictionaries. Each dictionary has keys 'value' and 'weight' with the exact numbers.

2

Set the maximum weight capacity

Create a variable called max_weight and set it to 50

DSA Python

items = [
    {'value': 60, 'weight': 10},
    {'value': 100, 'weight': 20},
    {'value': 120, 'weight': 30}
]
# Set the maximum weight the bag can carry
# Your code here

Hint

Just create a variable named max_weight and assign it the number 50.

3

Calculate maximum value using fractional knapsack logic

Calculate the maximum value that fits in the bag by: first adding a key 'ratio' to each item as value divided by weight, then sorting items by 'ratio' in descending order, then iterating over items with variables item and adding as much value as possible without exceeding max_weight. Store the total value in a variable called total_value.

DSA Python

items = [
    {'value': 60, 'weight': 10},
    {'value': 100, 'weight': 20},
    {'value': 120, 'weight': 30}
]
max_weight = 50
# Calculate 'ratio' for each item
# Sort items by 'ratio' descending
# Use a loop with variable 'item' to pick items or fractions
# Calculate total_value
# Your code here

Hint

Calculate ratio for each item, sort by ratio descending, then pick items fully or partially until the bag is full.

4

Print the maximum total value

Print the variable total_value rounded to 2 decimal places using print(f"{total_value:.2f}")

DSA Python

items = [
    {'value': 60, 'weight': 10},
    {'value': 100, 'weight': 20},
    {'value': 120, 'weight': 30}
]
max_weight = 50

for item in items:
    item['ratio'] = item['value'] / item['weight']

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

total_value = 0.0
remaining_weight = max_weight

for item in items:
    if item['weight'] <= remaining_weight:
        total_value += item['value']
        remaining_weight -= item['weight']
    else:
        fraction = remaining_weight / item['weight']
        total_value += item['value'] * fraction
        break

# Print the total_value rounded to 2 decimals
# Your code here

Hint

Use an f-string to print total_value rounded to 2 decimal places.

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