Python 中标签的最大值

假设我们有一组项目：第 i 个项目的价值为 values[i]，标签为 labels[i]。然后，我们将选择这些项目的一个子集 S，使得：

  • |S| <= num_wanted
  • 对于每个标签 L，在 S 中具有标签 L 的项目数量 <= use_limit。

我们必须找到子集 S 的最大可能总和。

例如，如果输入类似于 values = [5,4,3,2,1] 和 labels = [1,1,2,2,3]，num_wanted = 3，use_limit = 1，则输出将为 9。这是因为选择的子集是第一个、第三个和第五个项目。

为了解决这个问题，我们将遵循以下步骤：

  • 创建一个数组 v
  • 对于 i 从 0 到 values 的长度
    • 将 [values[i], labels[i]] 插入 v
  • 对 v 数组进行排序
  • ans := 0, use := 空映射，i := 0
  • 当 num_wanted 和 i < v 的长度
    • 如果 use 映射中不存在 v[i, 1]
      • 将 num_wanted 减 1
      • ans := ans + v[i, 0]
      • use[v[i, 1]] := 1
    • 否则 use[v[i, 1]] < use_limit
      • 将 num_wanted 减 1
      • ans := ans + v[i, 0]
      • 将 use[v[i, 1]] 加 1
    • 将 i 加 1
  • 返回 ans

让我们来看下面的实现，以便更好地理解：

示例

 在线演示

class Solution(object):
   def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
      v = []
      for i in range(len(values)):
         v.append([values[i],labels[i]])
      v = sorted(v,key = lambda v:v[0],reverse=True)
      ans = 0
      use = {}
      i = 0
      while num_wanted and i < len(v):
         if v[i][1] not in use:
            num_wanted -=1
            ans+=v[i][0]
            use[v[i][1]] = 1
         elif use[v[i][1]]<use_limit:
            num_wanted -=1
            ans+=v[i][0]
            use[v[i][1]]+=1
         i+=1
      return ans
ob = Solution()
print(ob.largestValsFromLabels([5,4,3,2,1],[1,1,2,2,3],3,1))

输入

[5,4,3,2,1]
[1,1,2,2,3]
3
1

输出

9

更新于：2020年4月30日

129 次查看

开启您的职业生涯

完成课程获得认证

开始
广告