Question

2548. 填满背包的最大价格

English Version

题目描述

给定一个二维整数数组 items ，其中 items[i] = [pricei, weighti] 表示第 i 个物品的价格和重量。

还给定一个 正 整数容量 capacity 。

每个物品可以分成两个部分，比率为 part1 和 part2 ，其中 part1 + part2 == 1 。

• 第一个物品的重量是 weighti * part1 ，价格是 pricei * part1 。
• 同样，第二个物品的重量是 weighti * part2 ，价格是 pricei * part2 。

使用给定的物品，返回填满容量为 capacity 的背包所需的 最大总价格 。如果无法填满背包，则返回 -1 。与实际答案的差距在 10-5 以内的 实际答案 将被视为接受。

 

示例 1 ：

输入：items = [[50,1],[10,8]], capacity = 5
输出：55.00000
解释：
我们将第二个物品分成两个部分，part1 = 0.5，part2 = 0.5。 
第一个物品的价格和重量分别为 5 和 4 。同样地，第二个物品的价格和重量也是 5 和 4 。 
经过操作后，数组 items 变为 [[50,1],[5,4],[5,4]] 。 
为了填满容量为 5 的背包，我们取价格为 50 的第一个元素和价格为 5 的第二个元素。 
可以证明，55.0 是我们可以达到的最大总价值。

示例 2 ：

输入：items = [[100,30]], capacity = 50
输出：-1.00000
解释：无法用给定的物品装满背包。

 

提示：

• 1 <= items.length <= 105
• items[i].length == 2
• 1 <= pricei, weighti <= 104
• 1 <= capacity <= 109

解法

方法一：贪心 + 排序

我们将物品按照单位价格从大到小排序，然后依次取出物品，直到背包装满。

若最后背包未装满，则返回 $-1$，否则返回总价格。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为物品数量。

class Solution:
  def maxPrice(self, items: List[List[int]], capacity: int) -> float:
    ans = 0
    for p, w in sorted(items, key=lambda x: x[1] / x[0]):
      v = min(w, capacity)
      ans += v / w * p
      capacity -= v
    return -1 if capacity else ans

class Solution {
  public double maxPrice(int[][] items, int capacity) {
    Arrays.sort(items, (a, b) -> a[1] * b[0] - a[0] * b[1]);
    double ans = 0;
    for (var e : items) {
      int p = e[0], w = e[1];
      int v = Math.min(w, capacity);
      ans += v * 1.0 / w * p;
      capacity -= v;
    }
    return capacity > 0 ? -1 : ans;
  }
}

class Solution {
public:
  double maxPrice(vector<vector<int>>& items, int capacity) {
    sort(items.begin(), items.end(), [&](const auto& a, const auto& b) { return a[1] * b[0] < a[0] * b[1]; });
    double ans = 0;
    for (auto& e : items) {
      int p = e[0], w = e[1];
      int v = min(w, capacity);
      ans += v * 1.0 / w * p;
      capacity -= v;
    }
    return capacity > 0 ? -1 : ans;
  }
};

func maxPrice(items [][]int, capacity int) (ans float64) {
  sort.Slice(items, func(i, j int) bool { return items[i][1]*items[j][0] < items[i][0]*items[j][1] })
  for _, e := range items {
    p, w := e[0], e[1]
    v := min(w, capacity)
    ans += float64(v) / float64(w) * float64(p)
    capacity -= v
  }
  if capacity > 0 {
    return -1
  }
  return
}

function maxPrice(items: number[][], capacity: number): number {
  items.sort((a, b) => a[1] * b[0] - a[0] * b[1]);
  let ans = 0;
  for (const [p, w] of items) {
    const v = Math.min(w, capacity);
    ans += (v / w) * p;
    capacity -= v;
  }
  return capacity ? -1 : ans;
}