Python에서 용량 내에서 다른 항목을 취하여 얻을 수 있는 최대 금액을 찾는 프로그램

<시간/>

길이가 같은 가중치와 값이라는 두 개의 목록과 용량 k라는 또 다른 숫자가 있다고 가정합니다. 여기서 weights[i]와 values[i]는 i번째 항목의 가중치와 값을 보여줍니다. 이제 우리는 최대 k개의 용량 가중치를 취할 수 있고 각 항목의 최대 하나의 사본만 취할 수 있으므로 얻을 수 있는 최대 가치를 찾아야 합니다.

따라서 입력이 weight =[2, 3, 4], values =[2, 6, 4], capacity =6인 경우 출력은 8

이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n:=가중치 크기
dp:=크기 용량 x n의 행렬, 0으로 채움
0에서 n 사이의 i에 대해
- 0에서 용량 범위의 j에 대해 다음을 수행합니다.
  - i가 0과 같거나 j가 0과 같으면
    - dp[i, j]:=0
  - 그렇지 않으면 weight[i-1] <=j, then
    - dp[i,j] =(dp[i-1, j-weights[i-1]] + values[i-1]) 및 (dp[i-1, j])의 최대값
  - 그렇지 않으면
    - dp[i, j]:=dp[i-1, j]
반환 dp[n, 용량]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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