Pythonの容量内でさまざまなアイテムを取得することで取得できる最大量を見つけるためのプログラム

同じ長さの重みと値と呼ばれる2つのリストと、容量kと呼ばれる別の数があるとします。ここで、weights[i]とvalues[i]は、i番目のアイテムの重みと値を示しています。これで、最大でk個の容量の重みを取得でき、各アイテムの最大で1つのコピーしか取得できないため、取得できる値の最大量を見つける必要があります。

したがって、入力が重み=[2、3、4]、値=[2、6、4]、容量=6のような場合、出力は8になります

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

• n：=おもりのサイズ
• dp：=サイズ容量x nの行列で、0で埋めます
• 0からnの範囲のiについては、
  • 0から容量までの範囲のjについては、
    • iが0と同じか、jが0と同じ場合、
      • dp [i、j]：=0
    • それ以外の場合、weights [i-1] <=jの場合、
      • dp [i、j] =（dp [i-1、j-weights [i-1]] + values [i-1]）および（dp [i-1、j]）の最大値
      >
    • それ以外の場合、
      • dp [i、j]：=dp [i-1、j]
• return dp [n、capacity]

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

例

class Solution:
   def solve(self, weights, values, capacity):
      n=len(weights)
      dp=[[0 for i in range(capacity+1)]
      for _ in range(n+1)]
         for i in range(n+1):
            for j in range(capacity+1):
               if i==0 or j==0:
                  dp[i][j]=0
                  elif weights[i-1]<=j:
                     dp[i][j]=max(dp[i-1][j-weights[i-1]]+values[i-1],dp[i-1][j])
                  else:
                     dp[i][j]=dp[i-1][j]
      return dp[n][capacity]
ob = Solution() weights = [2, 3, 4] values = [2, 6, 4]
capacity = 6
print(ob.solve(weights, values, capacity))

入力

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

出力

8