下载掌阅APP，畅读海量书库
立即打开
有一组项目：第 i 个项目具有值value[ i ]和标签label[ i ]。选择这些项目的子集 S ，满足： S 的大小最大为num_wanted；并且对于每个标签 L ，带有标签 L 的 S 中的项目数最多为use_limit。返回子集 S 的最大可能和。
输入：值=[5，4，3，2，1]，标签=[1，1，2，2，3]，num_wanted=3，use_limit=1
输出：9
说明：选择的子集是第一、第三和第五项。
思路：对于值从大到小排列，然后从数组里面取值，注意每个数值的label不能超过use_limit。可以利用哈希表来统计每个数值的label值。
首先把值和相对应的标签成对放在一起，按值从小到大进行排序。因此我们得到[（1，3），（2，2），（3，2），（4，1），（5，1）]。
第一步：把（5，1）弹出来，此时label=1的个数还是0，小于use_limit；然后把label=1的计数器增加为1，所以5可以加入列表，res=[5]。
第二步：把（4，1）弹出来，此时label=1的计数器为1，不小于use_limit。
第三步：把（3，2）弹出来，此时label=2的计数器为0，小于use_limit；然后把label=2的计数器增加为1，所以3可以加入列表，res=[5，3]。
第四步：把（2，2）弹出来，此时label=2的计数器为1，等于use_limit。
第五步：把（1，3）弹出来，此时label=3的计数器为0，小于use_limit；然后把label=3的计数器增加为1，所以1可以加入列表，res=[5，3，1]。
因此最后列表元素的和就是9=5+3+1。
示例代码如下。
代码清单6-10 标签中的最大值
该方法的时间复杂度是 O （ n ），空间复杂度是 O （ n ）。