Pythonで複数のコピーを取得することにより、ナップサック問題で取得できる最大値を見つけるプログラム

重みと値と呼ばれる同じ長さの2つのリストがあり、別の値容量もあるとします。ここで、weights[i]とvalues[i]は、i番目のアイテムの重みと値を表します。最大で容量の重みを取得でき、アイテムごとに任意の数のコピーを取得できる場合は、取得できる最大の価値を見つける必要があります。

したがって、入力が重み=[1、2、3]、値=[1、5、3]、容量=5のような場合、出力は11

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

• 関数dp（）を定義します。これにはi、kが必要です
• iがウェイトのサイズと同じである場合、
  • 0を返す
• ans：=dp（i + 1、k）
• k> =weights [i]の場合、
  • ans：=ansとdp（i、k-重み[i]）+値の最大値[i]
• 回答を返す
• メインの方法から次のようにします-
• return dp（0、capacity）

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

例

class Solution:
   def solve(self, weights, values, capacity):
      def dp(i, k):
         if i == len(weights):
            return 0
         ans = dp(i + 1, k)
         if k >= weights[i]:
            ans = max(ans, dp(i, k - weights[i]) + values[i])
         return ans
      return dp(0, capacity)
ob = Solution()
weights = [1, 2, 3]
values = [1, 5, 3]
capacity = 5
print(ob.solve(weights, values, capacity))

入力

[1, 2, 3], [1,5,3], 5

出力

11