분할 가능 배낭 문제(Fractional Knapsack Problem)

분할 가능 배낭 문제(Fractional Knapsack Problem)

• 0-1 배낭 문제 에서 다음 조건 추가
  • 주어진 물건(O)을 원하는 형태로 얼마든지 분할 할 수 있음.
    • 각 물건의 일부분만을 배낭에 담을 수 있음.
• 실생활의 예)
  • 상인이 기름, 곡물, 밀가루와 같은 품목을 다룰 경우
    • 각 품목을 원하는 양만큼 덜어내서 배낭에 담을 수 있음.
• 일반 배낭 문제가 NP-완전 문제 인 것과 달리 분할 가능 문제 는 간단한 솔루션이 존재함.
  • 각 물건을 단위 무게(W)당 가격(V)을 기준으로 정렬함.
  • 그리디 방식 에 따라 단위 무게당 가격이 높은 순서 로 물건을 선택함.

분할 가능 배낭 문제의 예

• 배낭 용량(T)이 8인 경우에 선택할 수 있는 최선의 물건 조합

 

코드

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

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;
}

// 분할 가능 배낭 문제 알고리즘 구현 함수
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;
}

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

    std::vector<int> weights {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, weights[i], values[i]));
    }

    // 사용할 수 있는 물건 정보 출력
    std::cout << "[사용할 수 있는 물건 정보]" << std::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;

    return 0;
}

 

결과

[사용할 수 있는 물건 정보]
[1] 가격: 10    무게: 1 kg      단위 무게 당 가격: 10
[2] 가격: 7     무게: 2 kg      단위 무게 당 가격: 3.5
[3] 가격: 15    무게: 5 kg      단위 무게 당 가격: 3
[4] 가격: 10    무게: 9 kg      단위 무게 당 가격: 1.11111
[5] 가격: 12    무게: 2 kg      단위 무게 당 가격: 6
[6] 가격: 11    무게: 3 kg      단위 무게 당 가격: 3.66667
[7] 가격: 5     무게: 4 kg      단위 무게 당 가격: 1.25

[배낭에 넣을 물건들 (최대 용량 = 7)]
[1] 가격: 10    무게: 1 kg      단위 무게 당 가격: 10
[5] 가격: 12    무게: 2 kg      단위 무게 당 가격: 6
[6] 가격: 11    무게: 3 kg      단위 무게 당 가격: 3.66667
[2] 가격: 3.5   무게: 1 kg      단위 무게 당 가격: 3.5