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 次檢視

開啟您的職業生涯

完成課程獲得認證

開始
廣告