C++ implementation of knapsack branch and bound

Question

I am trying to a C++ implementation of this knapsack problem using branch and bounding. There is a Java version on this website here: Implementing branch and bound for knapsack

I'm trying to make my C++ version print out the 90 that it should, however it's not doing that, instead, it's printing out 5.

Does anyone know where and what the problem may be?

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

struct node
{
    int level;
    int profit;
    int weight;
    int bound;
};

int bound(node u, int n, int W, vector<int> pVa, vector<int> wVa)
{
    int j = 0, k = 0;
    int totweight = 0;
    int result = 0;

    if (u.weight >= W)
    {
        return 0;
    }
    else
    {
        result = u.profit;
        j = u.level + 1;
        totweight = u.weight;

        while ((j < n) && (totweight + wVa[j] <= W))
        {
            totweight = totweight + wVa[j];
            result = result + pVa[j];
            j++;
        }

        k = j;

        if (k < n)
        {
            result = result + (W - totweight) * pVa[k]/wVa[k];
        }
        return result;
    }
}

int knapsack(int n, int p[], int w[], int W)
{
    queue<node> Q;
    node u, v;
    vector<int> pV;
    vector<int> wV;
    Q.empty();

    for (int i = 0; i < n; i++)
    {
        pV.push_back(p[i]);
        wV.push_back(w[i]);
    }

    v.level = -1; 
    v.profit = 0;
    v.weight = 0;

    int maxProfit = 0;

    //v.bound = bound(v, n, W, pV, wV);
    Q.push(v);

    while (!Q.empty())
    {
        v = Q.front();
        Q.pop();

        if (v.level == -1)
        {
            u.level = 0;
        }
        else if (v.level != (n - 1))
        {
            u.level = v.level + 1;
        }

        u.weight = v.weight + w[u.level];
        u.profit = v.profit + p[u.level];

        u.bound = bound(u, n, W, pV, wV);

        if (u.weight <= W && u.profit > maxProfit)
        {
            maxProfit = u.profit;
        }

        if (u.bound > maxProfit)
        {
            Q.push(u);
        }

        u.weight = v.weight;
        u.profit = v.profit;

        u.bound = bound(u, n, W, pV, wV);

        if (u.bound > maxProfit)
        {
            Q.push(u);
        }
    }
    return maxProfit;
}

int main()
{
    int maxProfit;
    int n = 4;
    int W = 16;
    int p[4] = {2, 5, 10, 5};
    int w[4] = {40, 30, 50, 10};

    cout << knapsack(n, p, w, W) << endl;

    system("PAUSE");
}

Answer 1

I think you have put the profit and weight values in the wrong vectors. Change:

int p[4] = {2, 5, 10, 5};
int w[4] = {40, 30, 50, 10};

to:

int w[4] = {2, 5, 10, 5};
int p[4] = {40, 30, 50, 10};

and your program will output 90.

Answer 2

I believe what you are implementing is not a branch & bound algorithm exactly. It is more like an estimation based backtracking if I have to match it with something.

The problem in your algorithm is the data structure that you are using. What you are doing is to simply first push all the first levels, and then to push all second levels, and then to push all third levels to the queue and get them back in their order of insertion. You will get your result but this is simply searching the whole search space.

Instead of poping the elements with their insertion order what you need to do is to branch always on the node which has the highest estimated bound. In other words you are always branching on every node in your way regardless of their estimated bounds. Branch & bound technique gets its speed benefit from branching on only one single node each time which is most probable to lead to the result (has the highest estimated value).

Example : In your first iteration assume that you have found 2 nodes with estimated values

node1: 110

node2: 80

You are pushing them both to your queue. Your queue became "n2-n1-head" In the second iteration you are pushing two more nodes after branching on node1:

node3: 100

node4: 95

and you are adding them to you queue as well("n4-n3-n2-head". There comes the error. In the next iteration what you are going to get will be node2 but instead it should be node3 which has the highest estimated value.

So if I don't miss something in your code both your implementation and the java implementation are wrong. You should rather use a priority queue (heap) to implement a real branch & bound.

Answer 3

You are setting the W to 16, so the result is 5. The only item you can take into the knapsack is item 3 with profit 5 and weight 10.

Answer 4

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

struct Item
{
    float weight;
    int value;
};
struct Node
{
    int level, profit, bound;
    float weight;
};

bool cmp(Item a, Item b)
{
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}
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    = totweight + arr[j].weight;
        profit_bound = profit_bound + arr[j].value;
        j++;
    }
    if (j < n)
        profit_bound = 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;
    u.level = -1;
    u.profit = u.weight = 0;
    Q.push(u);
    int maxProfit = 0;
    while (!Q.empty())
    {
        u = Q.front();
        Q.pop();
        if (u.level == -1)
            v.level = 0;

        if (u.level == n-1)
            continue;
        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);
        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 = 55;   // Weight of knapsack
    Item arr[] = {{10, 60}, {20, 100}, {30, 120}};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    return 0;
}
**SEE IF THIS HELPS**