Pythonでアイテムをバッグに入れることで得られる最高価格を見つけるプログラム

番号のリストが2つあるとします。 1つは重みと呼ばれ、もう1つは値と呼ばれます。これらは同じ長さです。容量とカウントという2つの値もあります。ここで、weights[i]とvalues[i]は、i番目のアイテムの重みと値を表します。最大で最大容量重量、最大で合計数のアイテムを保持でき、各アイテムのコピーは1つしか取得できないため、取得できる最大の価値を見つける必要があります。

したがって、入力が重み=[2、2、4、6]値=[15、15、20、35]容量=8カウント=3のような場合、最初の3つの項目を選択できるため、出力は50になります。 、総重量が8であるため。

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

• items：=重みと値をとったペアのリスト

• 関数dp（）を定義します。これにはi、cp、ctが必要です

• iがアイテムのサイズと同じであるか、ctが0と同じである場合、

  • 0.0を返す

• （w、v）：=items [i]

• ans：=dp（i + 1、cp、ct）

• cp> =wの場合、

  • ans：=ansの最大値、dp（i + 1、cp --w、ct --1）+ v

• ansを返す

• メインメソッドからdp（0、capacity、count）を返します

例

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

class Solution:
   def solve(self, weights, values, capacity, count):
      items = list(zip(weights, values))
      def dp(i, cp, ct):
         if i == len(items) or ct == 0:
            return 0.0
         w, v = items[i]
         ans = dp(i + 1, cp, ct)
         if cp >= w:
            ans = max(ans, dp(i + 1, cp - w, ct - 1) + v)
         return ans
      return int(dp(0, capacity, count))
ob = Solution()
weights = [2, 2, 4, 6]
values = [15, 15, 20, 35]
capacity = 8
count = 3
print(ob.solve(weights, values, capacity, count))

入力

[2, 2, 4, 6], [15, 15, 20, 35], 8, 3

出力

50