그리디 알고리즘 (2) - 분할 가능 배낭 문제

 

 

그리디 - 분할 가능 배낭 문제

 

 

 그리디 방법으로 풀 수 있는 문제로 널리 알려진 배낭 문제에 대해 알아보겠다.

먼저 0-1 배낭 문제(0-1 knapsack problem)이라고도 부르는 일반 배낭 문제는

NP-완전 문제로 알려져 있어 다항 시간 솔루션을 사용할 수 없다.

그러나 0-1 배낭 문제를 조금 변경한

분할 가능 배낭(fractional kanpsack problem)은 그리디 방식으로 해결할 수 있다.

이 두 가지 문제를 살펴보면서,

문제 정의의 작은 차이가 문제 해결 방법에 큰 변화를 가져올  수 있다는 점을 확인하자.

 

 

0-1 배낭 문제

 

 물건들의 집합 O = { ... }이 있고,

여기서 i번째 물건 O[i]의 무게는, W[i]이고, 가격은 V[i]이다.

그리고 최대 무게를 T까지 견딜 수 있는 가방 (배낭)이 하나 주어진다.

이제 물건들을 가방에 담아야 하는데, 가방에 넣은 물건들의 가격 합이 최대가 되도록 물건을 선택하려고 한다.

단, 물건들의 무게 합이 T를 넘지 않아야 한다.

 

 예를 들어 여러분이 무역을 하는 상인이고,

매출의 일정 비율을 이익으로 가져간다면,

이익을 극대화하기 위해서 최대한 값 비싼 물건들을 가지고 다니면서 팔아야 하지만,

여러분이 사용할 수 있는 운송수단 (또는 배낭)에는 최대 T 무게까지의 물건만 실을 수 있다.

각각의 물건에 대한 무게와 가격을 이미 알고 있다면,

물건들을 어떻게 조합해서 가지고 다녀야 전체 물건 가격이 최대가 될까?

 

이러한 배낭 문제의 예를 표로 나타낸다면 다음과 같을 것이다.

 

 

배낭 문제는 NP - 완전 문제로 알려져 있으며,

이 문제에 대한 다항 시간 솔루션은 알려져 있지 않다.

결과적으로 모든 가능한 조합을 조사하여 무게가 T를 넘지 않는 가장 높은 가격을 찾아야 한다.

위 표는 무게가 8이 되는 두 가지의 물건 조합을 보여준다.

그림의 왼족 표에서 회색으로 표시된 항목이 배낭에 넣을 물건이다.

첫 번째 표에서는 전체 가격이 40이며, 두 번째 표에서는 전체 가격이 37이다.

그러므로 첫 번째 표에 나타난 물건 선택 방법이 두 번째보다 더 나은 선택이다.

최선의 물건 조합을 찾으려먼 모든 가능한 물건 조합 목록을 만들고,

그중 가격이 최대인 조합을 찾아야 한다.

 

분할 가능 배낭 문제

 

 이제는 앞서 설명한 일반 배낭 문제를 조금 바꾸어 분할 가능 배낭 문제로

주어진 물건을 원하는 형태로 얼마든지 분할할 수 있고, 각 물건의 일부분만을 배낭에 담을 수 있다고 가정해보자.

 

실생활의 예를 들면, 상인이 기름, 곡물, 밀가루와 같은 품목을 다룬다고 생각하면 된다.

이 경우 각 품목을 워하는 먕만큼 덜어내서 배낭에 담을 수 있다.

 

일반 배낭 문제가 NP-완전인 것과 달리 분할 가능 배낭 문제는 간단한 솔루션이 존재한다.

각 물건을 단위 무게당 가격을 기준으로 정렬하고,

그리디 방식에 따라 단위 무게당 가격이 높은 순서로 물건을 선택한다.

아래 표에서는 배낭 용량이 8인 경우에 선택할 수 있는 최선의 물건 조합을 보여준다.

그림의 왼족 표에서 단위 무게당 가격이 비싼 물건들을 위주로 선택된 것을 확인할 수 있다.

 

 

 

 

 

연습 문제 : 분할 가능 배낭 문제

 

 

이번 연습 문제에서는 표를 예시로 들었던 문제들을 

실제 C++ 프로그램으로 구현하여 결과를 확인해보겠다.

 

 

1. 먼저 필요한 헤더 파일을 포함하고, 객체를 표현할 Object 구조체를 정의한다.

 

#include <iostream>
#include <vector>
#include <algorithm>


struct Object
{
    int id;
    int weight;
    double value;
    double value_per_unit_weight;

    Object(int i, int w, double v) : id(i), weight(w), value(v), value_per_unit_weight(v /w){}

    // std::sort()에서 사용
    inline bool operator < (const Object& obj) const
    {
        return this->value_per_unit_weight < obj.value_per_unit_weight;
    }

    // 콘솔 출력 지원 std::cout << obj << std::endl; 코드 사용 가능
    friend std::ostream& operator<<(std::ostream& os, const Object& obj);
};

std::ostream& operator<<(std::ostream& os, const Object& obj)
{
    os << "[ " << obj.id << " ] 가격  : " << obj.value << " \t무게 : " << obj.weight << " kg\t 단위 무게 당 가격 : " << obj.value_per_unit_weight;
    return os;
}

 

 

Object 객체는 int 타입으로 무게와 가격 정보를 저장하고,

이로부터 단위 무게당 가격을 구하여 double 타입으로 저장한다.

 

 

2. 다음은 분할 가능 배낭 문제의 솔루션을 구하는 함수이다.

 

//분할 가능 배낭 문제 알고리즘 구현 함수
auto fill_knapsack(std::vector<Object>& objects, int knapsack_capacity)
{
    std::vector<Object> knapsack_contents;
    knapsack_contents.reserve(objects.size());

    // 물건들을 내림차순으로 정렬 (단위 무게 당 가격 기준)
    std::sort(objects.begin(), objects.end());
    std::reverse(objects.begin(), objects.end());

    // '가장 가치 있는' 물건들 먼저 배낭에 추가
    auto current_object = objects.begin();
    int current_total_weight = 0;
    while (current_total_weight < knapsack_capacity && current_object != objects.end())
    {
        knapsack_contents.push_back(*current_object);
        
        current_total_weight += current_object->weight;
        current_object++;
    }

    // 마지막에 추가한 물건에 의해 배낭 최대 허용 무게가 초과된 경우
    int weight_of_last_obj_to_remove = current_total_weight - knapsack_capacity;
    Object& last_object = knapsack_contents.back();
    if (weight_of_last_obj_to_remove > 0)
    {
        last_object.weight -= weight_of_last_obj_to_remove;
        last_object.value -= last_object.value_per_unit_weight * weight_of_last_obj_to_remove;
    }

    return knapsack_contents;
}

 

 

이 함수에서는 단위 무게당 가격을 기준으로 물건들을 내림차순 정렬한 후,

배낭 최대 용량이 될 때까지 물건을 채워 넣는다.

만약 배낭에 넣은 물건의 무게 합이 배낭 최대 무게를 초과될 때까지 물건을 채워 넣는다.

만약 배낭에 넣은 물건이 무게 합이 배낭 최대 무게를 초과할 경우

마지막에 넣은 물건을 일부 덜어내어 배낭 최대 무게에 맞도록 설정한다.

 

 

3. main() 함수에 테스트를 위한 코드를 추가한다.

 

int main(void)
{
    std::vector<Object> objects;
    objects.reserve(7);

    std::vector<int> weight{ 1, 2, 5, 9, 2, 3, 4 };
    std::vector<double> values{10, 7, 15, 10, 12, 11, 5};
    for (auto i = 0; i < 7; i++)
    {
        objects.push_back(Object(i + 1, weight[i], values[i]));
    }

    // 사용할 수 있는 물건 정보 출력
    std::cout << "[ 사용할 수 있는 물건 정보 ] " << endl;
    for (auto& o : objects)
        std::cout << o << std::endl;
    std::cout << std::endl;

    // 분할 가능 배낭 문제 알고리즘 실행, 배낭의 최대 허용 무게는 7로 지정
    int knapsack_capacity = 7;
    auto solution = fill_knapsack(objects, knapsack_capacity);

    // 배낭에 넣을 물건 정보 출력
    std::cout << "[배낭에 넣을 물건들 ( 최대 용량 = " << knapsack_capacity << " ] " << std::endl;
    for (auto& o : solution)
        std::cout << o << std::endl;
    std::cout << std::endl;

 

main() 함수에서 그림 5-5에 나타난 것과 같이 일곱 개의 물건 객체를 생성한다.

그리고 앞서 구현한 분할 가능 배낭 문제 알고리즘 함수 fill_knapsack() 함수를 호출하여

문제를 해결하고, 그 결과를 출력한다.

다만, 위 표와 조금 다르게 배낭의 최대 허용 무게를 7로 설정하여 결과를 확인해본다면,

 

 

다음과 같은 결과 화면을 확인할 수 있다.

이처럼 분할하여 물건의 일부만 배낭에 담는다는 점이 0-1 배낭 문제와는 다르다