Maximum price to fill a bag

Array Greedy Sorting

64.6% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_price(items: Vec<Vec<i32>>, capacity: i32) -> f64 {
    let total_weight: i64 = items.iter().map(|x| x[1] as i64).sum();
    if total_weight < capacity as i64 {
      return -1.0;
    }
    // Sort by price/weight ratio descending
    let mut items: Vec<(f64, f64)> = items.iter().map(|x| (x[0] as f64, x[1] as f64)).collect();
    items.sort_by(|a, b| (b.0 / b.1).partial_cmp(&(a.0 / a.1)).unwrap());
    let mut remaining = capacity as f64;
    let mut total_price = 0.0;
    for (price, weight) in &items {
      if remaining <= 0.0 {
        break;
      }
      if *weight <= remaining {
        total_price += price;
        remaining -= weight;
      } else {
        total_price += price * remaining / weight;
        remaining = 0.0;
      }
    }
    total_price
  }
}