[LeetCode] 1090. Largest Values From Labels

[grandyang]

We have a set of items: the i-th item has value values[i] and label labels[i].

Then, we choose a subset S of these items, such that:

• |S| <= num_wanted
• For every label L, the number of items in S with label L is <= use_limit.

Return the largest possible sum of the subset S.

Example 1:

Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], `num_wanted` = 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.

Example 2:

Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], `num_wanted` = 3, use_limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.

Example 3:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], `num_wanted` = 3, use_limit = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.

Example 4:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], `num_wanted` = 3, use_limit = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth item.

Note:

1. 1 <= values.length == labels.length <= 20000
2. 0 <= values[i], labels[i] <= 20000
3. 1 <= num_wanted, use_limit <= values.length

这道题说是给了一堆物品，每个物品有不同的价值和标签，分别放在 values 和 labels 数组中，现在让选不超过 num_wanted 个物品，且每个标签类别的物品不超过 use_limit，问能得到的最大价值是多少。说实话这道题博主研究了好久才弄懂题意，而且主要是看例子分析出来的，看了看踩比赞多，估计许多人跟博主一样吧。这道题可以用贪婪算法来做，因为需要尽可能的选价值高的物品，但同时要兼顾到物品的标签种类。所以可以将价值和标签种类组成一个 pair 对儿，放到一个优先队列中，这样就可以按照价值从高到低进行排列了。同时，由于每个种类的物品不能超过 use_limit 个，所以需要统计每个种类被使用了多少次，可以用一个 HashMap 来建立标签和其使用次数之间的映射。先遍历一遍所有物品，将价值和标签组成 pair 对儿加入优先队列中。然后进行循环，条件是 num_wanted 大于0，且队列不为空，此时取出队顶元素，将其标签映射值加1，若此时仍小于 use_limit，说明当前物品可以入选，将其价值加到 res 中，并且 num_wanted 自减1即可，参见代码如下：

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
        int res = 0, n = values.size();
        priority_queue<pair<int, int>> pq;
        unordered_map<int, int> useMap;
        for (int i = 0; i < n; ++i) {
            pq.push({values[i], labels[i]});
        }
        while (num_wanted > 0 && !pq.empty()) {
            int value = pq.top().first, label = pq.top().second; pq.pop();
            if (++useMap[label] <= use_limit) {
                res += value;
                --num_wanted;
            }
        }
        return res;
    }
};

Github 同步地址:

#1090

参考资料：

https://leetcode.com/problems/largest-values-from-labels/

https://leetcode.com/problems/largest-values-from-labels/discuss/312720/C%2B%2B-Greedy

https://leetcode.com/problems/largest-values-from-labels/discuss/313011/Question-Explanation-and-Simple-Solution-or-Java-or-100

LeetCode All in One 题目讲解汇总(持续更新中...)