가중치와 값이라고 하는 길이가 같은 두 개의 목록이 있고 또 다른 가치 용량이 있다고 가정합니다. 여기서 weights[i]와 values[i]는 i번째 항목의 가중치와 값을 나타냅니다. 최대 용량 가중치를 사용할 수 있고 각 항목에 대해 원하는 만큼의 사본을 사용할 수 있다면 얻을 수 있는 최대 가치를 찾아야 합니다.
따라서 입력이 weight =[1, 2, 3], values =[1, 5, 3], capacity =5인 경우 출력은 11
이 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- dp() 함수를 정의합니다. 이것은 i, k 가 걸립니다.
- i가 weight의 크기와 같으면
- 0을 반환
- ans :=dp(i + 1, k)
- k>=weights[i]이면
- ans :=ans 및 dp(i, k - weights[i]) + values[i]의 최대값
- 반환
- 메인 방법에서 다음을 수행하십시오 -
- 반환 dp(0, 용량)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
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