2548. 填满背包的最大价格 🔒

题目描述

给定一个二维整数数组 items ，其中 items[i] = [price_i, weight_i] 表示第 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 <= 10⁵
items[i].length == 2
1 <= price_i, weight_i <= 10⁴
1 <= capacity <= 10⁹

解法

方法一：贪心 + 排序

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

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

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

Python3JavaC++GoTypeScript

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;
}

2548. 填满背包的最大价格 🔒

题目描述

解法

方法一：贪心 + 排序

评论