문제 설명
두 개의 숫자 리스트가 주어진다고 가정해 보겠습니다. 하나는 weights(무게), 다른 하나는 values(가치)이며, 두 리스트의 길이는 서로 같습니다. 또한 capacity(최대 용량)와 count(최대 개수)라는 두 값도 함께 주어집니다. 여기서 weights[i]와 values[i]는 i번째 물건의 무게와 가치를 각각 나타냅니다.
우리는 담은 물건들의 총 무게가 capacity를 넘지 않고, 물건의 개수가 count를 넘지 않도록 가방에 담아야 합니다. 단, 각 물건은 최대 한 번만 선택할 수 있습니다. 이 조건 안에서 얻을 수 있는 최대 가치를 구하는 것이 이 문제의 목표입니다.
예를 들어 입력이 weights = [2, 2, 4, 6], values = [15, 15, 20, 35], capacity = 8, count = 3이라면 출력은 50이 됩니다. 첫 세 개의 물건을 선택하면 총 무게가 2 + 2 + 4 = 8로 용량과 정확히 일치하고, 가치의 합은 15 + 15 + 20 = 50이 되기 때문입니다.
풀이 접근 방식
이 문제는 대표적인 배낭(Knapsack) 문제의 변형으로, 재귀 호출을 이용한 동적 계획법(DP)으로 자연스럽게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- weights와 values를 zip으로 묶어 (무게, 가치) 쌍의 리스트인 items를 만듭니다.
- dp(i, cp, ct) 함수를 정의합니다. i는 현재 검토 중인 물건의 인덱스, cp는 남은 용량, ct는 앞으로 선택할 수 있는 남은 개수입니다.
- i가 items의 크기와 같거나 ct가 0이면 더 이상 담을 수 없으므로 0.0을 반환합니다.
- (w, v) := items[i]로 현재 물건의 무게와 가치를 꺼냅니다.
- ans := dp(i + 1, cp, ct) — 현재 물건을 선택하지 않는 경우의 결과입니다.
- 만약 cp >= w라면(남은 용량이 충분하다면) ans := max(ans, dp(i + 1, cp - w, ct - 1) + v) — 현재 물건을 선택하는 경우와 비교하여 더 큰 값을 저장합니다.
- ans를 반환합니다.
- 메인 메서드에서는 dp(0, capacity, count)를 반환합니다.
즉, dp 함수는 각 물건마다 "담는다"와 "담지 않는다" 두 가지 선택지를 모두 탐색하면서, 용량과 개수 제한을 지키는 범위 내에서 최댓값을 찾아냅니다.
예시 코드
다음 구현을 통해 더 잘 이해할 수 있습니다.
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
성능 개선 팁
위 구현은 모든 조합을 탐색하는 재귀 방식이므로 시간 복잡도는 O(2^n)입니다. 물건의 개수가 많아지면 실행 시간이 급격히 늘어날 수 있으므로, Python의 functools.lru_cache 데코레이터를 사용해 dp 함수에 메모이제이션을 적용하면 이미 계산한 상태를 재사용하여 성능을 크게 향상시킬 수 있습니다.