LeetCode 2548 - Maximum Price to Fill a Bag
The problem is asking us to maximize the total price of items placed in a bag with a fixed capacity. Each item is defined by a price and a weight, but unlike traditional knapsack problems, items can be divided proportionally, meaning we can take fractions of an item.
Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting
Solution
Problem Understanding
The problem is asking us to maximize the total price of items placed in a bag with a fixed capacity. Each item is defined by a price and a weight, but unlike traditional knapsack problems, items can be divided proportionally, meaning we can take fractions of an item. Specifically, if we take a fraction f of an item, we gain f * price for f * weight. The goal is to fill the bag to its capacity in a way that maximizes the total price.
The input consists of a list of items, each with a positive integer price and weight, and a positive integer capacity. The output is a float representing the maximum price achievable, or -1 if it is impossible to fill the bag (for example, if all items are individually heavier than the capacity and we cannot combine them to exactly match the capacity).
Constraints are large: up to 10^5 items, each with price and weight up to 10^4, and capacity up to 10^9. This implies that any naive approach that tries all combinations is infeasible.
Important edge cases include items whose weights exceed the capacity individually, items whose total weight is less than the capacity, or cases where fractional selection is necessary to exactly reach the capacity.
Approaches
The brute-force approach would try every combination of items and their possible fractions to fill the bag exactly. This would involve enumerating subsets and solving a continuous fraction problem for each subset, which is exponentially slow and infeasible given the constraints.
The key observation is that the problem is a fractional knapsack problem. In fractional knapsack, to maximize total value with divisible items, we should take items in order of decreasing price-per-weight ratio. We take as much as possible of the highest ratio items until the capacity is filled. This greedy approach works because any deviation from choosing the highest ratio first would yield a lower total price.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Try all subsets and fractional divisions, infeasible for n up to 10^5 |
| Optimal (Greedy) | O(n log n) | O(1) or O(n) | Sort items by price-per-weight ratio and pick greedily |
Algorithm Walkthrough
- Compute the price-per-weight ratio for each item. This represents the value gained per unit weight.
- Sort the items in descending order of price-per-weight ratio. This ensures that the items with the highest return on weight are considered first.
- Initialize
total_price = 0andremaining_capacity = capacity. - Iterate over the sorted items. For each item:
a. If the item's weight is less than or equal to the remaining capacity, take the whole item, subtract its weight from remaining_capacity, and add its price to total_price.
b. If the item's weight exceeds the remaining capacity, take only the fraction that fits. Compute the fraction as remaining_capacity / item_weight, add fraction * item_price to total_price, and set remaining_capacity = 0.
5. After the loop, if remaining_capacity is still positive, return -1 because the bag could not be fully filled. Otherwise, return total_price.
Why it works: The greedy choice property guarantees that selecting the highest price-per-weight first always maximizes the total price. Since items can be split, taking fractions ensures that we can always reach exactly the bag's capacity if the total weight of items is sufficient.
Python Solution
from typing import List
class Solution:
def maxPrice(self, items: List[List[int]], capacity: int) -> float:
# Compute price per weight for each item
items = [(price / weight, price, weight) for price, weight in items]
# Sort by price per weight descending
items.sort(reverse=True, key=lambda x: x[0])
total_price = 0.0
remaining_capacity = capacity
for ratio, price, weight in items:
if remaining_capacity == 0:
break
if weight <= remaining_capacity:
total_price += price
remaining_capacity -= weight
else:
fraction = remaining_capacity / weight
total_price += price * fraction
remaining_capacity = 0
return total_price if remaining_capacity == 0 else -1.0
The Python code first calculates the value density (price per weight) for each item and sorts them. Then, it iterates through the items, fully taking an item if it fits, or partially taking a fraction if needed. The final check ensures that the bag was filled; if not, it returns -1.
Go Solution
import "sort"
func maxPrice(items [][]int, capacity int) float64 {
type Item struct {
ratio float64
price int
weight int
}
n := len(items)
arr := make([]Item, n)
for i, it := range items {
arr[i] = Item{
ratio: float64(it[0]) / float64(it[1]),
price: it[0],
weight: it[1],
}
}
sort.Slice(arr, func(i, j int) bool {
return arr[i].ratio > arr[j].ratio
})
totalPrice := 0.0
remainingCapacity := capacity
for _, item := range arr {
if remainingCapacity == 0 {
break
}
if item.weight <= remainingCapacity {
totalPrice += float64(item.price)
remainingCapacity -= item.weight
} else {
fraction := float64(remainingCapacity) / float64(item.weight)
totalPrice += fraction * float64(item.price)
remainingCapacity = 0
}
}
if remainingCapacity > 0 {
return -1.0
}
return totalPrice
}
The Go implementation mirrors Python but uses a struct for clarity. Sorting and fraction calculations are handled with float64 to maintain precision. Go requires explicit casting for division to avoid integer truncation.
Worked Examples
Example 1:
items = [[50,1],[10,8]], capacity = 5
Compute ratios: [50/1=50, 10/8=1.25]
Sort: [[50,1], [10,8]]
- Take first item fully: remaining capacity = 5-1=4, total_price = 50
- Take second item fraction: fraction = 4/8 = 0.5, total_price += 10*0.5 = 5 → total_price = 55
- Bag is full → return 55.0
Example 2:
items = [[100,30]], capacity = 50
- Single item weight 30 < 50 → take fully, remaining capacity = 50-30 = 20
- No more items → bag not full → return -1.0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting n items dominates; iteration is O(n) |
| Space | O(n) | Storing ratios in a new list or struct |
The algorithm is efficient for the problem constraints, handling up to 10^5 items without issue.
Test Cases
# provided examples
assert abs(Solution().maxPrice([[50,1],[10,8]], 5) - 55.0) < 1e-5 # fractional selection
assert abs(Solution().maxPrice([[100,30]], 50) + 1.0) < 1e-5 # impossible to fill
# edge cases
assert abs(Solution().maxPrice([[10,5]], 5) - 10.0) < 1e-5 # exactly fits
assert abs(Solution().maxPrice([[10,5]], 3) - 6.0) < 1e-5 # partial fraction
assert abs(Solution().maxPrice([[10,5],[20,10]], 15) - 30.0) < 1e-5 # multiple items
assert abs(Solution().maxPrice([[10,5],[20,10]], 50) + 1.0) < 1e-5 # not enough total weight
| Test | Why |
|---|---|
| Fractional selection | Verifies partial items are handled |
| Impossible fill | Bag cannot be completely filled |
| Exact fit | Weight matches capacity exactly |
| Multiple items | Confirms greedy selection over multiple items |
| Insufficient total weight | Total items cannot fill bag, should return -1 |
Edge Cases
Single item fits exactly: If the bag capacity equals the weight of one item, the algorithm correctly takes it fully and returns its price. A naive implementation might incorrectly try to split it.
Item weight larger than capacity: When all items are heavier than the bag, the algorithm will take only a fraction. If no combination can fill the bag completely, it correctly returns -1.
Large number of items: With n up to 10^5, efficiency matters. Sorting ensures we process items in order of value density without enumerating subsets. The fractional approach guarantees correctness without exhaustive search.