Pythonでいくつかの割り当てを完了することによって取得できる最大のクレジットを見つけるためのプログラム

同じサイズの2つのリストがあり、これらは期限とクレジットであり、コースの割り当てを表しているとします。ここで、deadlines [i]は割り当てiの期限日を示し、credits[i]は割り当てiで取得するクレジットの量を表します。課題を完了する日は1日あり、締め切り日の前または締め切り日に完了することができます。複数の割り当てを同時に実行することはできません。課題のサブセットを完了することで獲得できる最大のクレジットを見つける必要があります。

したがって、入力が期限=[1、2、2、2]クレジット=[4、5、6、7]のようである場合、0日目にクレジット5で割り当てを完了することができるため、出力は18になります。 1日目にクレジット6で割り当て、3日目にクレジット7で割り当てを完了します。

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

• a：=期限とクレジットのペアを作成し、クレジットに基づいて降順で並べ替えます
• aが空の場合、
  • 0を返す
• res：=サイズのリスト（1 +期限の最大値）と0で埋める
• ans：=0
• aの各ペア（i、j）について、実行します
  • iから0までの範囲のkについては、1ずつ減らします。
    • res [k]が0の場合、
      • res [k]：=1
      • ans：=ans + j
      • ループから抜け出す
• 回答を返す

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

例

class Solution:
   def solve(self, deadlines, credits):
      a = sorted(list(zip(deadlines, credits)), key=lambda x: x[1], reverse=True)
      if not a:
         return 0
      res = [0] * (max(deadlines) + 1)
      ans = 0
      for i, j in a:
         for k in range(i, -1, -1):
            if not res[k]:
               res[k] = 1
               ans += j
               break
      return ans
     
ob = Solution()
deadlines = [1, 2, 2, 2]
credits = [4, 5, 6, 7]
print(ob.solve(deadlines, credits))

入力

[1, 2, 2, 2], [4, 5, 6, 7]

出力

18