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

Giả sử chúng ta có một tập hợp các mục:mục thứ i có các giá trị value [i] và các nhãn nhãn [i]. Sau đó, chúng tôi sẽ lấy một tập hợp con S của các mục này, sao cho -

• | S | <=num_wised
• Đối với mọi nhãn L, số lượng mục có trong S có nhãn L là <=use_limit.

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

Ví dụ:nếu đầu vào là các giá trị =[5,4,3,2,1] và các nhãn là [1,1,2,2,3], num_wworthy =3, use_limit =1, thì đầu ra sẽ là 9 . Điều này là do tập hợp con được chọn trong mục đầu tiên, thứ ba và thứ năm.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một mảng v
• cho tôi trong phạm vi từ 0 đến độ dài của các giá trị
  • chèn [giá trị [i], nhãn [i]] vào v
• sắp xếp mảng v
• ans:=0, sử dụng:=bản đồ trống và i:=0
• while num_w prefer and i
• nếu v [i, 1] không có trong bản đồ sử dụng
  • giảm num_w mong muốn đi 1
  • ans:=ans + v [i, 0]
  • sử dụng [v [i, 1]]:=1
• khác sử dụng [v [i, 1]]
• giảm num_w mong muốn đi 1
• ans:=ans + v [i, 0]
• tăng mức sử dụng [v [i, 1]] lên 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu ra

9