문제 소개
길이가 같은 두 리스트 weights와 values, 그리고 정수 capacity가 주어집니다. weights[i]와 values[i]는 각각 i번째 아이템의 무게와 가치를 의미합니다. 이 문제의 핵심 조건은 각 아이템을 여러 개의 복사본으로 자유롭게 선택할 수 있다는 점입니다. 즉, 총 무게가 capacity를 초과하지 않는 범위 안에서 아이템을 담아 얻을 수 있는 최대 가치를 구하는 프로그램을 작성해야 합니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
- weights = [1, 2, 3]
- values = [1, 5, 3]
- capacity = 5
이때 출력은 11입니다. 무게 2인 아이템을 2개(가치 10) 선택하고, 무게 1인 아이템을 1개(가치 1) 추가로 담으면 총 무게가 5가 되면서 가치 11이라는 최대값을 얻을 수 있습니다.
풀이 접근 방법
이 문제는 전형적인 무한 배낭 문제(Unbounded Knapsack)이며, 재귀 함수 기반의 동적 계획법(DP)으로 깔끔하게 해결할 수 있습니다. 풀이 단계는 다음과 같습니다.
- 함수
dp(i, k)를 정의합니다. 이 함수는 i번째 아이템부터 고려하고 남은 용량이 k일 때 얻을 수 있는 최대 가치를 반환합니다. - i가 weights의 길이와 같다면 더 이상 선택할 아이템이 없으므로 0을 반환합니다.
- 먼저 i번째 아이템을 건너뛰는 경우의 값을 계산합니다:
ans = dp(i + 1, k) - 남은 용량 k가 weights[i] 이상이라면, i번째 아이템을 하나 더 담는 경우
dp(i, k - weights[i]) + values[i]와 비교해 더 큰 값을 ans에 저장합니다. 여기서 인덱스를 i 그대로 유지하기 때문에 같은 아이템을 반복해서 선택할 수 있으며, 이것이 바로 여러 복사본 허용 조건을 처리하는 핵심입니다. - ans를 반환합니다.
- 메인 로직에서는
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
성능 개선 팁: 메모이제이션 적용
위의 순수 재귀 풀이는 같은 하위 문제를 반복해서 계산할 수 있어 입력이 커지면 비효율적입니다. 파이썬의 functools.lru_cache 데코레이터를 활용해 메모이제이션을 적용하면, 이미 계산한 dp(i, k) 결과를 재활용할 수 있습니다. 이렇게 하면 시간 복잡도가 대략 O(n × capacity) 수준으로 줄어들어 훨씬 빠르게 동작합니다.
from functools import lru_cache
class Solution:
def solve(self, weights, values, capacity):
@lru_cache(maxsize=None)
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)
이처럼 무한 배낭 문제는 재귀 관계식만 명확히 세우면 직관적으로 구현할 수 있으며, 메모이제이션을 더하면 실전에서도 충분히 효율적으로 활용할 수 있습니다.