You are given a 2D integer array items where items[i] = [pricei, weighti] denotes the price and weight of the ith item, respectively.
You are also given a positive integer capacity.
Each item can be divided into two items with ratios part1 and part2, where part1 + part2 == 1.
weighti * part1 and the price of the first item is pricei * part1.weighti * part2 and the price of the second item is pricei * part2.Return the maximum total price to fill a bag of capacity capacity with given items. If it is impossible to fill a bag return -1. Answers within 10-5 of the actual answer will be considered accepted.
Example 1:
Input: items = [[50,1],[10,8]], capacity = 5 Output: 55.00000 Explanation: We divide the 2nd item into two parts with part1 = 0.5 and part2 = 0.5. The price and weight of the 1st item are 5, 4. And similarly, the price and the weight of the 2nd item are 5, 4. The array items after operation becomes [[50,1],[5,4],[5,4]]. To fill a bag with capacity 5 we take the 1st element with a price of 50 and the 2nd element with a price of 5. It can be proved that 55.0 is the maximum total price that we can achieve.
Example 2:
Input: items = [[100,30]], capacity = 50 Output: -1.00000 Explanation: It is impossible to fill a bag with the given item.
Constraints:
1 <= items.length <= 105items[i].length == 21 <= pricei, weighti <= 1041 <= capacity <= 109Problem Overview: You are given items where each item has a price and weight, along with a bag capacity. You may take fractional parts of items. The goal is to maximize the total price while filling the bag exactly to the given capacity.
Approach 1: Brute Force Enumeration (Exponential Time, O(2^n) time, O(n) space)
A naive strategy tries every possible combination of items and fractions to determine the maximum achievable value. Conceptually, you explore each item choice recursively and decide how much of that item to include. Because items can be partially taken, the search space grows extremely quickly and becomes impractical even for moderate input sizes. This approach mainly helps understand the decision space and why a smarter strategy is required. Interviewers rarely expect this implementation but discussing it shows awareness of the problem’s combinatorial nature.
Approach 2: Greedy + Sorting (Optimal) (O(n log n) time, O(1) extra space)
This problem is a direct application of the fractional knapsack principle. The key insight is that items with the highest price / weight ratio provide the most value per unit of capacity. Compute this ratio for every item, then sort the items in descending order of that ratio using sorting. Iterate through the sorted list and greedily take as much weight as possible from each item. If the current item fully fits, add its full value and reduce the remaining capacity. If it does not fit, take only the fraction needed to fill the remaining capacity and stop.
This greedy strategy works because each unit of capacity should always be assigned to the most valuable available item. Sorting ensures you always pick the best option first. The implementation uses a simple iteration over the sorted array of items, and the greedy choice guarantees optimality for fractional knapsack problems. If you exhaust all items before filling the bag, return -1 because the bag cannot be completely filled.
Recommended for interviews: Interviewers expect the greedy + sorting solution. It demonstrates recognition of the fractional knapsack pattern and the ability to translate the value-per-weight insight into code. Mentioning the brute force idea shows you considered the full search space, but implementing the greedy ratio-based strategy proves you understand why the optimal solution works.
We sort the items in descending order by unit price, and then take out the items one by one until the backpack is full.
If the backpack is not full in the end, return -1, otherwise return the total price.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the number of items.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(2^n) | O(n) | Conceptual understanding of exploring all combinations; not practical for real constraints |
| Greedy + Sorting by Price/Weight Ratio | O(n log n) | O(1) extra (sorting dependent) | Optimal solution for fractional knapsack problems where items can be partially taken |
leetcode 2548. Maximum Price to Fill a Bag - sort with specified key • Code-Yao • 136 views views
Watch 2 more video solutions →Practice Maximum Price to Fill a Bag with our built-in code editor and test cases.
Practice on FleetCode