Pythonのラベルからの最大値

アイテムのセットがあるとします。i番目のアイテムには値values[i]とラベルlabels[i]があります。次に、これらのアイテムのサブセットSを取得します。たとえば、-

• | S | <=num_wanted
• ラベルLごとに、ラベルLのSに存在するアイテムの数は<=use_limitです。

サブセットSの可能な最大の合計を見つける必要があります。

たとえば、入力がvalues =[5,4,3,2,1]のようで、ラベルが[1,1,2,2,3]、num_wanted =3、use_limit =1の場合、出力は9になります。 。これは、1番目、3番目、5番目の項目でサブセットが選択されたためです。

これを解決するには、次の手順に従います-

• 1つのアレイを作成するv
• 0から値の長さの範囲のiの場合
  • [values [i]、labels[i]]をvに挿入
• v配列を並べ替える
• ans：=0、：=空のマップを使用、i：=0
• num_wantedおよびi
• v [i、1]が使用マップに存在しない場合
  • num_wantedを1減らします
  • ans：=ans + v [i、0]
  • use [v [i、1]]：=1
• else use [v [i、1]]
• num_wantedを1減らします
• ans：=ans + v [i、0]
• use [v [i、1]]を1増やします

理解を深めるために、次の実装を見てみましょう-

例

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