Problem Description

You have a collection of items, each with a specific price and weight. Your goal is to fill a bag that has a limited capacity to maximize the total value.

Given:

• A 2D array items where items[i] = [price_i, weight_i] represents the price and weight of the i-th item
• A positive integer capacity representing the maximum weight the bag can hold

Key rules:

• Each item can be divided into smaller portions (fractional parts are allowed)
• When you take a fraction of an item, both its weight and price are scaled proportionally
  • For example, taking half of an item means taking half its weight and getting half its price
• You need to maximize the total price while ensuring the total weight doesn't exceed the bag's capacity

The problem asks you to return the maximum total price you can achieve by filling the bag. If it's impossible to completely fill the bag to its exact capacity, return -1.

This is essentially the fractional knapsack problem where items can be broken into smaller pieces. The greedy approach works here: prioritize items with the highest value-to-weight ratio (unit price), taking as much of each item as possible until the bag reaches its capacity limit.

Example: If you have an item with price 10 and weight 5, its unit price is 10/5 = 2. If you can only fit weight 3 in your bag, you'd take 3/5 of the item, getting a price of 10 * (3/5) = 6.

Intuition

When we can break items into smaller pieces, the strategy becomes clear: we want to get the most value for every unit of weight we put in the bag. Think of it like shopping with a limited budget - you'd want to buy items that give you the best "bang for your buck."

The key insight is to calculate the unit price (value per weight) for each item: price/weight. This tells us how much value we get for each unit of weight. An item with price 10 and weight 2 has a unit price of 10/2 = 5, meaning we get 5 units of value for every 1 unit of weight.

Since we can take fractional parts of items, we should greedily take items with the highest unit price first. This is different from the classic 0/1 knapsack problem where items can't be divided - there, greedy doesn't always work because you might need to skip a high-value heavy item for multiple lighter items.

Here's the thought process:

1. Sort all items by their unit price in descending order
2. Take items one by one, starting with the highest unit price
3. For each item, take as much as possible (either the whole item or just enough to fill the remaining capacity)
4. Continue until the bag is exactly full

The special constraint here is that we must fill the bag exactly to its capacity. If after taking all available items we still have unused capacity, it means it's impossible to exactly fill the bag, so we return -1.

For example, if the bag capacity is 10 and we only have items with total weight 8, we can't exactly fill it to 10, so the answer would be -1. This is why the solution checks if capacity becomes exactly 0 at the end.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy strategy with sorting to maximize the total price.

Step 1: Sort items by unit price

sorted(items, key=lambda x: x[1] / x[0])

We sort the items by their weight-to-price ratio weight/price in ascending order. This is equivalent to sorting by unit price price/weight in descending order. Items with lower weight/price ratios have higher unit prices and should be selected first.

Step 2: Greedily select items

We iterate through the sorted items and for each item [p, w]:

v = min(w, capacity)

Calculate how much of the current item we can take. It's either:

• The entire item weight w if we have enough capacity
• The remaining capacity if the item is heavier than what we can carry

Step 3: Update total price and remaining capacity

ans += v / w * p
capacity -= v

• Add the proportional price to our answer: (v/w) * p where v/w is the fraction of the item taken
• Reduce the remaining capacity by the weight we just added

Step 4: Check if bag is exactly full

return -1 if capacity else ans

After processing all items:

• If capacity == 0, the bag is exactly full, return the total price ans
• If capacity > 0, we couldn't fill the bag completely, return -1

Time Complexity: O(n log n) where n is the number of items, dominated by the sorting step.

Space Complexity: O(1) if we don't count the space used for sorting (typically O(log n) for the sorting algorithm's recursion stack).

The algorithm guarantees the optimal solution because at each step, we're maximizing the value gained per unit of weight used, which is the optimal strategy when items can be fractionally divided.

Example Walkthrough

Let's work through a concrete example to illustrate the solution approach.

Given:

• items = [[60, 10], [100, 20], [120, 30]] (format: [price, weight])
• capacity = 50

Step 1: Calculate unit prices and sort

First, let's calculate the unit price (price/weight) for each item:

• Item 0: price=60, weight=10 → unit price = 60/10 = 6.0
• Item 1: price=100, weight=20 → unit price = 100/20 = 5.0
• Item 2: price=120, weight=30 → unit price = 120/30 = 4.0

Sort items by unit price (descending):

• Items after sorting: [[60, 10], [100, 20], [120, 30]] (already in the right order)

Step 2: Greedily fill the bag

Starting with capacity = 50 and total_price = 0:

Item 1 [60, 10]:

• Can we take all 10 units? Yes, because capacity (50) ≥ weight (10)
• Take entire item: v = min(10, 50) = 10
• Add to total: total_price = 0 + (10/10) × 60 = 60
• Update capacity: capacity = 50 - 10 = 40

Item 2 [100, 20]:

• Can we take all 20 units? Yes, because capacity (40) ≥ weight (20)
• Take entire item: v = min(20, 40) = 20
• Add to total: total_price = 60 + (20/20) × 100 = 160
• Update capacity: capacity = 40 - 20 = 20

Item 3 [120, 30]:

• Can we take all 30 units? No, because capacity (20) < weight (30)
• Take partial item: v = min(30, 20) = 20
• Fraction taken: 20/30 = 2/3
• Add to total: total_price = 160 + (20/30) × 120 = 160 + 80 = 240
• Update capacity: capacity = 20 - 20 = 0

Step 3: Check if bag is exactly full

Final capacity = 0, so the bag is exactly full. Return total_price = 240

The optimal solution takes all of items 1 and 2, plus 2/3 of item 3, achieving a maximum total price of 240.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the number of items. This is dominated by the sorting operation sorted(items, key=lambda x: x[1] / x[0]), which sorts the items based on their weight-to-price ratio. The subsequent iteration through the sorted list takes O(n) time, but this is overshadowed by the sorting cost.

The space complexity is O(log n). While the sorted() function creates a new list that would typically require O(n) space, the dominant space consideration for complexity analysis is the additional space used by the sorting algorithm itself. Python's Timsort algorithm uses O(log n) space for its recursive call stack during the sorting process. The variables ans, p, w, and v only require O(1) additional space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Division Instead of Float Division

Pitfall: Using integer division when calculating ratios or fractional values, which can lead to incorrect results due to truncation.

# Wrong - integer division in Python 2 or with // operator
amount_to_take = min(weight, capacity)
max_value += (amount_to_take // weight) * price  # Results in 0 for fractional amounts

Solution: Always use float division to maintain precision:

# Correct - ensures float division
max_value += (amount_to_take / weight) * price  # Properly handles fractions

2. Incorrect Sorting Key

Pitfall: Sorting by the wrong ratio or in the wrong order. Some might accidentally sort by weight/price in ascending order or price/weight in ascending order.

# Wrong - sorts by weight/price ascending (lowest unit price first)
sorted_items = sorted(items, key=lambda item: item[1] / item[0])

# Wrong - sorts by price/weight ascending (also lowest unit price first)  
sorted_items = sorted(items, key=lambda item: item[0] / item[1])

Solution: Sort by price/weight ratio in descending order to prioritize highest value items:

# Correct - highest value-to-weight ratio first
sorted_items = sorted(items, key=lambda item: item[0] / item[1], reverse=True)

3. Division by Zero Error

Pitfall: Not handling items with zero weight, which causes a division by zero error when calculating the ratio.

# Crashes if any item has weight = 0
sorted_items = sorted(items, key=lambda item: item[0] / item[1], reverse=True)

Solution: Filter out or handle zero-weight items separately:

# Option 1: Filter out zero-weight items
valid_items = [item for item in items if item[1] > 0]
sorted_items = sorted(valid_items, key=lambda item: item[0] / item[1], reverse=True)

# Option 2: Handle zero-weight items with special logic
def get_ratio(item):
    return float('inf') if item[1] == 0 else item[0] / item[1]
sorted_items = sorted(items, key=get_ratio, reverse=True)

4. Floating Point Precision Issues

Pitfall: Checking exact equality with floating point numbers when determining if capacity is exactly zero.

# May fail due to floating point arithmetic
if capacity == 0:  # Might be 0.0000000001 due to precision errors
    return max_value

Solution: Use an epsilon value for comparison:

EPSILON = 1e-9
if abs(capacity) < EPSILON:  # More robust comparison
    return max_value

5. Not Breaking Early When Capacity is Filled

Pitfall: Continuing to iterate through items even after the bag is full, which wastes computational resources.

# Inefficient - continues iterating unnecessarily
for price, weight in sorted_items:
    amount_to_take = min(weight, capacity)
    max_value += (amount_to_take / weight) * price
    capacity -= amount_to_take
    # Missing break condition

Solution: Add an early termination condition:

for price, weight in sorted_items:
    amount_to_take = min(weight, capacity)
    max_value += (amount_to_take / weight) * price
    capacity -= amount_to_take
  
    if capacity == 0:  # Stop once bag is full
        break