Skip to main content
Talentd

Maximum Price to Fill a Bag - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedySorting6 min readAsked at: Microsoft
Practice this problem

Problem Statement

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.

  • The weight of the first item is weighti * part1 and the price of the first item is pricei * part1.
  • Similarly, the weight of the second item is 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 <= 105
  • items[i].length == 2
  • 1 <= pricei, weighti <= 104
  • 1 <= capacity <= 109

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(2^n)O(n)Conceptual understanding of exploring all combinations; not practical for real constraints
Greedy + Sorting by Price/Weight RatioO(n log n)O(1) extra (sorting dependent)Optimal solution for fractional knapsack problems where items can be partially taken

Video Solution

leetcode 2548. Maximum Price to Fill a Bag - sort with specified key • Code-Yao • 137 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Maximum Price to Fill a Bag easy or hard?
Maximum Price to Fill a Bag is considered a Medium problem. The implementation is straightforward once you recognize it as a fractional knapsack variant, but identifying the greedy price-to-weight ratio insight is the key step.
Maximum Price to Fill a Bag Python/Java solution
Most implementations compute the ratio price/weight, sort the items by this value in descending order, and iterate through them while subtracting from the remaining capacity. The same greedy logic works consistently in Python, Java, C++, Go, and TypeScript.
How to solve Maximum Price to Fill a Bag in O(n)?
A strict O(n) approach is generally not used because sorting by value density is required to guarantee optimal selection order. The typical optimal solution is O(n log n) due to sorting. After sorting, the greedy filling step itself runs in O(n).
What is the best approach for Maximum Price to Fill a Bag?
The optimal approach uses a greedy strategy combined with sorting. Compute the price-to-weight ratio for each item, sort items in descending order of this ratio, and greedily take as much as possible from each item until the bag reaches capacity. This works because each unit of capacity should be filled with the item that provides the highest value per weight.
Is Maximum Price to Fill a Bag asked at Google/Amazon/Meta?
Problems based on the fractional knapsack greedy strategy frequently appear in interviews at companies like Amazon, Google, and Meta. The exact problem may vary, but the concept of maximizing value using a price-to-weight ratio is a common interview pattern.
What data structure is used in Maximum Price to Fill a Bag?
The main structure used is an array of items containing price and weight values. The array is sorted by price-to-weight ratio, then iterated greedily. No complex structures are required beyond sorting and basic arithmetic.
What is the time complexity of Maximum Price to Fill a Bag?
The optimal solution runs in O(n log n) time because the items must be sorted by their price-to-weight ratio. After sorting, a single linear scan fills the bag greedily. The space complexity is O(1) extra if sorting is done in-place.

Ready to solve this problem?

Practice Maximum Price to Fill a Bag with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays