Maximum Price to Fill a Bag
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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 * part1and the price of the first item ispricei * part1. - Similarly, the weight of the second item is
weighti * part2and the price of the second item ispricei * 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.
Examples
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 <= 10^5items[i].length == 21 <= pricei, weighti <= 10^41 <= capacity <= 10^9
Solution
Method 1 – Greedy (Fractional Knapsack)
Intuition
To maximize the total price, always take as much as possible from the item with the highest price per unit weight. This is the classic fractional knapsack problem, where we can take fractions of items.
Approach
- For each item, calculate its price per unit weight.
- Sort the items in descending order of price per unit weight.
- Initialize
ans = 0and iterate through the sorted items:- If the current item's weight is less than or equal to the remaining capacity, take the whole item and add its price to
ans. - Otherwise, take as much as possible (fractional part) to fill the bag and add the proportional price to
ans. - Stop when the bag is full.
- If the current item's weight is less than or equal to the remaining capacity, take the whole item and add its price to
- If the bag is not filled after all items, return -1. Otherwise, return
ans.
Code
C++
class Solution {
public:
double maximumPrice(vector<vector<int>>& items, int capacity) {
vector<pair<double, int>> v;
for (auto& it : items) v.push_back({(double)it[0]/it[1], v.size()});
sort(v.rbegin(), v.rend());
double ans = 0;
for (auto& [ratio, idx] : v) {
int w = items[idx][1], p = items[idx][0];
if (capacity >= w) {
ans += p;
capacity -= w;
} else {
ans += ratio * capacity;
capacity = 0;
break;
}
}
return capacity == 0 ? ans : -1;
}
};
Go
import "sort"
func maximumPrice(items [][]int, capacity int) float64 {
type pair struct{ratio float64; idx int}
v := make([]pair, len(items))
for i, it := range items {
v[i] = pair{float64(it[0])/float64(it[1]), i}
}
sort.Slice(v, func(i, j int) bool { return v[i].ratio > v[j].ratio })
ans := 0.0
for _, p := range v {
w, pr := items[p.idx][1], items[p.idx][0]
if capacity >= w {
ans += float64(pr)
capacity -= w
} else {
ans += p.ratio * float64(capacity)
capacity = 0
break
}
}
if capacity > 0 { return -1 }
return ans
}
Java
class Solution {
public double maximumPrice(int[][] items, int capacity) {
int n = items.length;
double[][] v = new double[n][2];
for (int i = 0; i < n; ++i) v[i] = new double[]{(double)items[i][0]/items[i][1], i};
Arrays.sort(v, (a, b) -> Double.compare(b[0], a[0]));
double ans = 0;
for (double[] p : v) {
int idx = (int)p[1];
int w = items[idx][1], pr = items[idx][0];
if (capacity >= w) {
ans += pr;
capacity -= w;
} else {
ans += p[0] * capacity;
capacity = 0;
break;
}
}
return capacity == 0 ? ans : -1;
}
}
Kotlin
class Solution {
fun maximumPrice(items: Array<IntArray>, capacity: Int): Double {
val v = items.mapIndexed { i, it -> Pair(it[0].toDouble()/it[1], i) }.sortedByDescending { it.first }
var cap = capacity
var ans = 0.0
for ((ratio, idx) in v) {
val w = items[idx][1]
val p = items[idx][0]
if (cap >= w) {
ans += p
cap -= w
} else {
ans += ratio * cap
cap = 0
break
}
}
return if (cap == 0) ans else -1.0
}
}
Python
class Solution:
def maximumPrice(self, items: list[list[int]], capacity: int) -> float:
v = sorted([(p/w, p, w) for p, w in items], reverse=True)
ans = 0.0
for ratio, p, w in v:
if capacity >= w:
ans += p
capacity -= w
else:
ans += ratio * capacity
capacity = 0
break
return ans if capacity == 0 else -1.0
Rust
impl Solution {
pub fn maximum_price(items: Vec<Vec<i32>>, mut capacity: i32) -> f64 {
let mut v: Vec<(f64, usize)> = items.iter().enumerate().map(|(i, it)| ((it[0] as f64)/(it[1] as f64), i)).collect();
v.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap());
let mut ans = 0.0;
for (ratio, idx) in v {
let w = items[idx][1];
let p = items[idx][0];
if capacity >= w {
ans += p as f64;
capacity -= w;
} else {
ans += ratio * capacity as f64;
capacity = 0;
break;
}
}
if capacity == 0 { ans } else { -1.0 }
}
}
TypeScript
class Solution {
maximumPrice(items: number[][], capacity: number): number {
const v = items.map((it, i) => [it[0]/it[1], i] as [number, number]).sort((a, b) => b[0] - a[0]);
let ans = 0;
for (const [ratio, idx] of v) {
const w = items[idx][1], p = items[idx][0];
if (capacity >= w) {
ans += p;
capacity -= w;
} else {
ans += ratio * capacity;
capacity = 0;
break;
}
}
return capacity === 0 ? ans : -1;
}
}
Complexity
- ⏰ Time complexity:
O(n log n), wherenis the number of items (for sorting). - 🧺 Space complexity:
O(n), for the sorted list of items.