C++ 그리디 알고리즘으로 분수 배낭 문제(Fractional Knapsack) 해결하기

분수 배낭 문제(Fractional Knapsack Problem)는 각각 무게와 가치를 가진 여러 아이템이 주어졌을 때, 배낭의 용량 한도 내에서 총가치를 최대화하는 문제입니다. 이 문제의 핵심은 아이템을 잘라서(부분적으로) 담을 수 있다는 점이며, 이러한 특성 덕분에 탐욕(Greedy) 알고리즘으로 최적해를 구할 수 있습니다.

문제 개념

0/1 배낭 문제와 달리, 분수 배낭 문제에서는 아이템 전체를 담지 못할 경우 일부만 잘라서 넣을 수 있습니다. 예를 들어 금가루나 쌀처럼 나눌 수 있는 물건을 생각하면 이해하기 쉽습니다.

탐욕적 접근 방식은 다음과 같습니다.

• 각 아이템에 대해 밀도(density) = 가치 ÷ 무게, 즉 단위 무게당 가치를 계산합니다.
• 아이템들을 밀도 기준으로 내림차순 정렬합니다.
• 정렬된 순서대로 아이템을 배낭에 담습니다.
• 배낭이 가득 차기 직전 남은 용량보다 다음 아이템이 크다면, 해당 아이템의 일부만 남은 용량만큼 잘라서 담고 종료합니다.

알고리즘 단계

시작
1. Item 구조체 배열을 선언한다 (가치 v, 무게 w, 밀도 d)
2. 각 아이템의 밀도 d = v / w 를 계산한다
3. 아이템 배열을 밀도 내림차순으로 정렬한다
4. 배열의 앞쪽부터 순서대로 아이템을 배낭에 담는다
   - 전체를 담을 수 있으면 통째로 담는다
   - 담을 수 없으면 남은 용량만큼만 잘라서 담는다
종료

C++ 예제 코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

typedef struct {
    int v;      // 가치 (value)
    int w;      // 무게 (weight)
    float d;    // 밀도 (density = v / w)
} Item;

// 아이템 입력 받기
void input(Item items[], int sizeOfItems) {
    cout << "Enter total " << sizeOfItems << " item's values and weight" << endl;
    for(int i = 0; i < sizeOfItems; i++) {
        cout << "Enter " << i+1 << " V ";
        cin >> items[i].v;
        cout << "Enter " << i+1 << " W ";
        cin >> items[i].w;
    }
}

// 입력된 데이터 출력
void display(Item items[], int sizeOfItems) {
    int i;
    cout << "values: ";
    for(i = 0; i < sizeOfItems; i++) {
        cout << items[i].v << "\t";
    }
    cout << endl << "weight: ";
    for (i = 0; i < sizeOfItems; i++) {
        cout << items[i].w << "\t";
    }
    cout << endl;
}

// 밀도 내림차순 비교 함수
bool compare(Item i1, Item i2) {
    return (i1.d > i2.d);
}

// 분수 배낭 알고리즘
float knapsack(Item items[], int sizeOfItems, int W) {
    int i;
    float totalValue = 0, totalWeight = 0;

    // 1단계: 각 아이템의 밀도 계산
    // v와 w가 모두 int이므로 float 형변환 필요
    for (i = 0; i < sizeOfItems; i++) {
        items[i].d = (float)items[i].v / items[i].w;
    }

    // 2단계: 밀도 기준 내림차순 정렬
    sort(items, items + sizeOfItems, compare);

    // 3단계: 정렬된 순서대로 배낭에 담기
    for(i = 0; i < sizeOfItems; i++) {
        if(totalWeight + items[i].w <= W) {
            // 아이템 전체를 담을 수 있는 경우
            totalValue += items[i].v;
            totalWeight += items[i].w;
        } else {
            // 남은 용량만큼 아이템을 잘라서 담는 경우
            int wt = W - totalWeight;
            totalValue += (wt * items[i].d);
            totalWeight += wt;
            break;
        }
    }

    cout << "Total weight in bag " << totalWeight << endl;
    return totalValue;
}

int main() {
    int W;
    Item items[4];
    input(items, 4);
    cout << "Entered data \n";
    display(items, 4);
    cout << "Enter Knapsack weight \n";
    cin >> W;
    float mxVal = knapsack(items, 4, W);
    cout << "Max value for " << W << " weight is " << mxVal;
}

실행 예시

가치와 무게가 다음과 같은 4개의 아이템이 있고, 배낭 용량이 50이라고 가정해 보겠습니다.

아이템 1: 가치 60, 무게 10  → 밀도 6.0
아이템 2: 가치 100, 무게 20 → 밀도 5.0
아이템 3: 가치 120, 무게 30 → 밀도 4.0
아이템 4: 가치 40, 무게 40  → 밀도 1.0

알고리즘 실행 과정은 다음과 같습니다.

• 밀도가 가장 높은 아이템 1을 통째로 담습니다. (무게 10, 가치 누적 60)
• 아이템 2를 통째로 담습니다. (무게 30, 가치 누적 160)
• 아이템 3은 무게 30으로 남은 용량 20보다 크므로, 20/30만큼 잘라서 담습니다. (120 × 20/30 = 80 추가)
• 배낭이 가득 찼으므로 종료합니다.

Total weight in bag 50
Max value for 50 weight is 240

핵심 포인트 정리

• 시간 복잡도: 정렬이 지배적이므로 O(n log n)입니다.
• 형변환 주의: (float)items[i].v / items[i].w처럼 반드시 float으로 형변환해야 정수 나눗셈으로 인한 오차를 막을 수 있습니다.
• 탐욕 선택의 타당성: 아이템을 자유롭게 나눌 수 있기 때문에, 단위 무게당 가치가 높은 것부터 담는 것이 항상 최적입니다. 반면 0/1 배낭 문제처럼 아이템을 나눌 수 없다면 동적 계획법(DP)이 필요합니다.