부분 배낭 문제란?
각각 고유한 가치(value)와 무게(weight)를 지닌 물건들의 목록이 주어지고, 최대 허용 무게가 W인 배낭에 이 물건들을 담는 상황을 생각해 봅시다. 부분 배낭 문제(Fractional Knapsack Problem)의 목표는 배낭에 담긴 물건들의 총 무게가 W를 초과하지 않는 조건에서 가치의 합을 최대한 크게 만드는 것입니다.
배낭 문제는 크게 두 가지 유형으로 나뉩니다.
- 0-1 배낭 문제(0-1 Knapsack) — 물건을 자를 수 없으므로 각 물건을 통째로 담거나 아예 담지 않아야 합니다.
- 부분 배낭 문제(Fractional Knapsack) — 물건을 원하는 만큼 잘라서 나누어 담을 수 있습니다.
이 글에서는 물건을 분할해 담을 수 있는 부분 배낭 문제를 다룹니다. 이 문제는 그리디(Greedy) 알고리즘으로 최적해를 보장할 수 있으며, 정렬 과정이 병목이 되므로 전체 시간 복잡도는 O(n log n)입니다.
입력 및 출력 예시
입력:
최대 무게 = 50, 물건 목록 (가치, 무게)
{(60, 10), (100, 20), (120, 30)}
출력:
최대 가치: 240
→ 무게 10, 20인 물건을 모두 담고, 무게 30인 물건은 2/3만큼 담은 경우
알고리즘 동작 방식
부분 배낭 문제는 다음 절차로 해결합니다.
- 각 물건의 단위 무게당 가치(가치 ÷ 무게)를 계산합니다.
- 이 비율이 높은 순서대로 물건 목록을 내림차순 정렬합니다.
- 비율이 높은 물건부터 차례로 배낭에 담습니다.
- 남은 용량보다 물건이 크면, 들어갈 수 있는 만큼만 잘라서 담고 반복을 종료합니다.
알고리즘 의사 코드
fractionalKnapsack(weight, itemList, n)
입력: 배낭의 최대 무게, 물건 목록, 물건의 개수
출력: 얻을 수 있는 최대 가치
Begin
sort the item list based on the ratio of value and weight
currentWeight := 0
knapsackVal := 0
for all items i in the list do
if currentWeight + weight of item[i] <= weight then
currentWeight := currentWeight + weight of item[i]
knapsackVal := knapsackVal + value of item[i]
else
remaining := weight – currentWeight
knapsackVal := knapsackVal + value of item[i] * (remaining / weight of item[i])
break the loop
done
End
C++ 구현 예시
#include <iostream>
#include <algorithm>
using namespace std;
struct item {
int value, weight;
};
// 가치 대비 무게 비율을 기준으로 두 물건을 비교
bool cmp(struct item a, struct item b) {
double aRatio = (double)a.value / a.weight;
double bRatio = (double)b.value / b.weight;
return aRatio > bRatio;
}
double fractionalKnapsack(int weight, item itemList[], int n) {
sort(itemList, itemList + n, cmp); // 비교 함수로 물건 목록 정렬
int currWeight = 0; // 배낭에 담긴 현재 무게
double knapsackVal = 0.0;
for (int i = 0; i < n; i++) { // 모든 물건을 순회
if (currWeight + itemList[i].weight <= weight) {
// 공간이 충분하면 물건 전체를 담는다
currWeight += itemList[i].weight;
knapsackVal += itemList[i].value;
} else {
// 물건 전체를 담을 공간이 없으면 일부만 잘라 담는다
int remaining = weight - currWeight;
knapsackVal += itemList[i].value * ((double)remaining / itemList[i].weight);
break;
}
}
return knapsackVal;
}
int main() {
int weight = 50; // 배낭의 최대 무게
item itemList[] = {{60, 10}, {100, 20}, {120, 30}};
int n = 3;
cout << "Maximum value: " << fractionalKnapsack(weight, itemList, n);
}
실행 결과
Maximum value: 240
예제 풀이 과정
위 예제를 단계별로 살펴보면 다음과 같습니다.
- 비율 계산: (60 ÷ 10) = 6, (100 ÷ 20) = 5, (120 ÷ 30) = 4 → 비율 순으로 정렬됨
- 무게 10짜리 물건 전체 담기 → 누적 가치 60, 남은 용량 40
- 무게 20짜리 물건 전체 담기 → 누적 가치 160, 남은 용량 20
- 무게 30짜리 물건은 20/30 = 2/3만큼만 담기 → 120 × 2/3 = 80 추가
- 최종 최대 가치 = 60 + 100 + 80 = 240
참고로 0-1 배낭 문제에서는 물건을 자를 수 없기 때문에 같은 그리디 방식이 최적해를 보장하지 못하며, 동적 계획법(DP)으로 풀어야 한다는 점도 함께 기억해 두면 좋습니다.