길이가 같은 두 개의 리스트 weights(무게)와 values(가치), 그리고 하나의 값 capacity(배낭 용량)가 주어졌다고 가정해 봅시다. weights[i]와 values[i]는 각각 i번째 아이템의 무게와 가치를 의미합니다.
이것은 대표적인 부분 배낭(Fractional Knapsack) 문제입니다. 아이템을 통째로 담지 못할 경우에는 일부만 잘라서 담을 수 있고, 이때 가치 역시 담은 비율에 비례하여 계산됩니다. 배낭의 최대 용량 안에서 얻을 수 있는 최대 가치를 구하고, 결과값은 소수점 이하를 버린 정수로 반환해야 합니다.
문제 예시
입력이 다음과 같다고 해봅시다.
weights = [6, 7, 3], values = [110, 120, 2], capacity = 10
이 경우 출력은 178입니다. 무게 6짜리 아이템(가치 110)을 통째로 담으면 남은 용량은 4가 되고, 무게 7짜리 아이템(가치 120)의 4/7만큼 담아 120 × 4/7 ≈ 68.57 → 68의 가치를 추가로 얻기 때문입니다.
해결 절차
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
res := 0으로 결과 변수를 초기화합니다.
무게와 가치를 짝지은 쌍(pair)들의 목록 P를 만들고, 단위 무게당 가치(가치 ÷ 무게)를 기준으로 내림차순 정렬합니다.
P의 각 쌍에 대해 다음을 반복합니다.
용량(capacity)이 0이면 반복문을 빠져나옵니다.
pair[0](무게) > capacity인 경우, res에 (pair[1] / (pair[0] / capacity))의 값을 더하고 capacity를 0으로 설정합니다. 즉, 남은 용량만큼 해당 아이템을 비율대로 잘라 담습니다.
pair[0] ≤ capacity인 경우, res에 pair[1] 전체 가치를 더하고 capacity에서 pair[0]을 차감합니다.
모든 과정이 끝나면 res의 소수점 이하를 버린 값(floor)을 반환합니다.
단위 가치가 높은 아이템부터 우선적으로 담는 것이 핵심 아이디어이며, 이 그리디 전략은 부분 배낭 문제에서 항상 최적해를 보장합니다.
구현 코드
아래 코드를 통해 실제 동작 방식을 확인해 보겠습니다.
class Solution: def solve(self, weights, values, capacity): res = 0 for pair in sorted(zip(weights, values), key=lambda x: - x[1]/x[0]): if not bool(capacity): break if pair[0] > capacity: res += int(pair[1] / (pair[0] / capacity)) capacity = 0 elif pair[0] <= capacity: res += pair[1] capacity -= pair[0] return int(res) ob = Solution() weights = [6, 7, 3] values = [110, 120, 2] capacity = 10 print(ob.solve(weights, values, capacity))
입력
[6, 7, 3], [110, 120, 2], 10
출력
178
코드 설명 및 시간 복잡도
코드의 핵심은 sorted(zip(weights, values), key=lambda x: - x[1]/x[0]) 부분입니다. 무게와 가치를 묶은 후 단위 무게당 가치가 높은 순서로 정렬하여, 가성비가 좋은 아이템부터 배낭에 채워 넣습니다.
아이템의 무게가 남은 용량보다 크면 필요한 만큼만 비율 계산(pair[1] / (pair[0] / capacity))을 통해 가치를 더하고, 그렇지 않으면 아이템 전체를 담습니다. 용량이 모두 소진되면 즉시 반복을 종료합니다.
정렬에 O(n log n), 순회에 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 이는 완전 탐색 기반의 0/1 배낭 문제(O(2ⁿ))와 달리 매우 효율적인 편입니다.