0/1 Knapsack Example

0/1 Knapsack Example using Branch&Bound

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

struct Item
{
    double weight;  // 무게
    int value;  // 가치
};

struct Node
{
    int level, profit, bound;
    double weight;
};

bool cmp(Item a, Item b)
{
    double r1 = a.value / a.weight;
    double r2 = b.value / b.weight;
    return r1 > r2;
}

// bounding function
int bound(Node u, int n, int W, Item arr[])
{
    if (u.weight >= W)    return 0;
    int profit_bound = u.profit;
    
    int j = u.level + 1;
    int totweight = u.weight;

    while ((j < n) && (totweight + arr[j].weight <= W))
    {
        totweight += arr[j].weight;
        profit_bound += arr[j].value;
        j++;
    }

    if (j < n)
        profit_bound += (W - totweight) * arr[j].value /
        arr[j].weight;

    return profit_bound;
}

int knapsack(int W, Item arr[], int n)
{
    sort(arr, arr + n, cmp);    // 단위무게당 가치 내림차순 정렬

    queue<Node> Q;
    Node u, v;

    // dummy node at starting
    u.level = -1;
    u.profit = u.weight = 0;
    Q.push(u);

    int maxProfit = 0;  // 현재까지 계산 node의 최대이익 
    while (!Q.empty())
    {
        u = Q.front();
        Q.pop();

        // current node가 시작node or leaf node인 경우
        if (u.level == -1) v.level = 0;
        if (u.level == n - 1) continue;

        // v는 u의 child 노드를 나타냄??
        v.level = u.level + 1;

        v.weight = u.weight + arr[v.level].weight;
        v.profit = u.profit + arr[v.level].value;

        if (v.weight <= W && v.profit > maxProfit) maxProfit = v.profit;

        v.bound = bound(v, n, W, arr);

        if (v.bound > maxProfit) Q.push(v);

        // right child node (Item 포함x인 경우)
        v.weight = u.weight;
        v.profit = u.profit;
        v.bound = bound(v, n, W, arr);
        
        if (v.bound > maxProfit) Q.push(v);
    }

    return maxProfit;
}

int main()
{
    int W = 10;   // Weight of knapsack
    Item arr[] = { {2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30} };    // {weight, profit}
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Maximum possible profit = " << knapsack(W, arr, n);

    return 0;
}