Pythonでトラックに乗せることができる最大ユニットを見つけるためのプログラム

boxTypesと呼ばれる2D配列として表されるボックスのセットがあるとします。ここで、boxTypes [i]には2つの要素[タイプiのボックスの数、タイプiのボックスあたりのユニット数]が含まれます。ここで、別の値kもあります。これは、そのトラックに置くことができるボックスの最大数です。ボックスの数がkを超えない限り、トラックに配置するボックスを選択できます。トラックに乗せることができるユニットの最大総数を見つける必要があります。

したがって、入力がboxTypes =[[2,4]、[3,3]、[4,2]]、k =6のような場合、出力は19になります。これは、

• タイプ1の2つのボックスで、それぞれに4つのユニットが含まれています

• タイプ2の3つのボックスで、それぞれに3つのユニットが含まれています

• タイプ3の4つのボックスで、それぞれに2つのユニットが含まれています

k =6として、タイプ1と2のすべてのボックス、およびタイプ3の1つのボックスのみを取ることができるため、（2 * 4）+（3 * 3）+ 2 =8 + 9 +2=19アイテムになります。 。

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

• 各ボックスに存在するアイテムの数に基づいてboxTypesを並べ替える

• 合計：=0、塗りつぶし：=0

• boxTypesの各iについて、実行します

  • fill + i [0] <=kの場合、

    • fill：=fill + i [0]

    • 合計：=合計+ i [0] * i [1]

  • それ以外の場合

    • 合計：=合計+（k-塗りつぶし）* i [1]

    • ループから出てきます

• 合計を返す

例（Python）

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

def solve(boxTypes, k):
   boxTypes.sort(key = lambda x : x[1], reverse = True)
   total = 0
   fill = 0
   for i in boxTypes:
      if fill + i[0] <= k:
         fill += i[0]
         total += i[0] * i[1]
      else:
         total += (k - fill) * i[1]
         break
   return total

boxTypes = [[2,4],[3,3],[4,2]]
k = 6
print(solve(boxTypes, k))

入力

[[2,4],[3,3],[4,2]], 6

出力

19