1090. Largest Values From Labels

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation