Giá trị lớn nhất từ nhãn trong Python

Giả sử có tập mục: mục i có giá trị values[i] và nhãn labels[i]. Ta lấy tập con S sao cho −

• |S| <= num_wanted
• Với mọi nhãn L, số mục trong S có nhãn L <= use_limit.

Ta phải tìm tổng lớn nhất có thể của tập con S.

Ví dụ, values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1, kết quả 9. Vì chọn mục thứ nhất, ba, năm.

Để giải quyết, ta làm theo các bước −

• tạo mảng v
• với i từ 0 đến len(values)
  • thêm [values[i], labels[i]] vào v
• sắp xếp v giảm dần theo giá trị
• ans := 0, use := map rỗng, i := 0
• khi num_wanted và i < len(v)
  • nếu v[i][1] không trong use
    • giảm num_wanted 1
    • ans := ans + v[i][0]
    • use[v[i][1]] := 1
  • ngược lại nếu use[v[i][1]] < use_limit
    • giảm num_wanted 1
    • ans := ans + v[i][0]
    • tăng use[v[i][1]] 1
  • tăng i 1
• trả về ans

Xem triển khai sau −

Ví dụ

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))

Đầu vào

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

Kết quả

9