0-1 배낭 문제(0-1 Knapsack Problem)

0-1 배낭 문제(0-1 Knapsack Problem)

• 조건
  • 물건들의 집합 O = {O₁, O₂, ..., On}이 있을 경우
    • Wi : i번째 물건 Oi의 무게
    • Vi : i번째 물건의 가격(Value)
  • 최대 무게를 T까지 견딜 수 있는 가방(배낭)이 1개 주어짐.
    • 물건들을 가방에 담아야 함.
      • 가방에 넣은 물건들의 가격(V) 합이 최대가 되도록 물건 선택
    • 단, 물건들의 무게 합이 T를 넘지 않아야 함.

예 : 무역을 하는 상인이 매출의 일정 비율을 이익으로 가져갈 떄

• 이익을 극대화하려면 최대한 비싼 물건들을 가지고 다니면서 팔아야 하지만, 사용할 수 있는 운송 수단(또는 배낭)에는 최대 T 무게까지의 물건말 실을 수 있음.
• 각각의 물건에 대한 무게(W)와 가격(V)은 이미 알고 있음.
• 물건들을 어떻게 조합해서 가지고 다녀야 전체 물건 가격(V)이 최대 가 되는지 정하는 문제

일반 배낭 문제의 예

• 배낭 문제는 NP-완전 문제 로 알려져 있음.
  • 이 문제에 대한 다항 시간 솔루션은 알려져 있지 않음.
• 결과적으로 모든 가능한 조합을 조사하여 무게가 T를 넘지 않는 가장 높은 가격을 찾아내야 함.
• 위의 그림은 8가지 물건 조합을 보여줌.
  • 노란색으로 색칠된 부분 : 배낭에 넣을 물건
  • 첫 번째 표에서의 전체 가격이 두 번째 표에서의 전체 가격보다 크므로 더 나은 선택이라고 할 수 있음.
• 최선의 물건 조합을 찾으려면 모든 가능한 물건 조합 목록을 만들고, 그중 가격이 최대인 조합을 찾아야 함.

 

코드

• 코드 출처 : click

#include <iostream>
#include <climits>

#define max(A, B) (A > B) ? A : B

int KnapSack01(int Value[], int Weights[], int n, int T) {
    if (T < 0) {
        return INT_MIN;
    }
    if (n < 0 || T == 0) {
        return 0;
    }

    int in = Value[n] + KnapSack01(Value, Weights, n - 1, T - Weights[n]);
    int ex = KnapSack01(Value, Weights, n - 1, T);
    return max(in, ex);
}

int main() {
    // Knapsack #1
    int v[] = {10, 7, 15, 10, 12, 11, 5};       // Values of Items
    int w[] = {1, 2, 5, 9, 2, 3, 4};            // Weights of Items
    int T = 8;                                  // Capacity of Knapsack
    int n = sizeof(v) / sizeof(v[0]);           // Size of Value Set
    std::cout << "Knapsack Value is " << KnapSack01(v, w, n - 1, T);

    return 0;
}

 

결과

Knapsack value is 40