두 개의 숫자 목록이 있다고 가정합니다. 하나는 가중치라고 하고 다른 하나는 값이라고 합니다. 이것들은 같은 길이이며, 우리는 또한 capacity와 count라는 두 개의 값을 가지고 있습니다. 여기서 weights[i]와 values[i]는 i번째 항목의 가중치와 값을 나타냅니다. 우리는 최대 용량 무게와 최대 합계 항목 수를 보유할 수 있으며 각 항목의 복사본을 하나만 가져갈 수 있으므로 얻을 수 있는 최대 가치를 찾아야 합니다.
따라서 입력이 weight =[2, 2, 4, 6] values =[15, 15, 20, 35] capacity =8 count =3인 경우 처음 3개 항목을 선택할 수 있으므로 출력은 50이 됩니다. , 총 무게가 8이기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
항목 :=가중치와 값을 취하여 쌍의 목록
-
dp() 함수를 정의합니다. i, cp, ct
가 필요합니다. -
i가 항목의 크기와 같거나 ct가 0과 같으면
-
0.0 반환
-
-
(w, v) :=항목[i]
-
답변 :=dp(i + 1, cp, ct)
-
cp> =w이면
-
ans :=ans의 최대값, dp(i + 1, cp - w, ct - 1) + v
-
-
반환
-
기본 메서드에서 dp(0, 용량, 개수)를 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
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