0/1 Knapsack Problem Using Branch And Bound C++

Suzhoumeite

6 min read

·

Jul 17, 2024

47

Share

0/1 Knapsack Problem using Branch and Bound in C++

The 0/1 Knapsack Problem is a classic problem in computer science and operations research that involves finding the optimal way to pack a set of items of different weights and values into a knapsack of limited capacity. In this article, we will discuss how to solve the 0/1 Knapsack Problem using the Branch and Bound algorithm in C++.

Problem Definition

Given a set of items, each with a weight w_i and a value v_i, determine the subset of items to include in a knapsack of capacity W to maximize the total value while not exceeding the knapsack capacity.

Formulation

Let x_i be a binary variable indicating whether item i is included in the knapsack or not. The 0/1 Knapsack Problem can be formulated as follows:

Maximize

∑ v_i * x_i

Subject to

∑ w_i * x_i ≤ W x_i ∈ {0, 1}

Branch and Bound Algorithm

The Branch and Bound algorithm is a systematic method for solving optimization problems by recursively exploring the solution space. The algorithm consists of two main components:

Upper Bound

The upper bound is an estimate of the maximum possible solution value. In the 0/1 Knapsack Problem, the upper bound can be calculated using the following formula:

UB = ∑ v_i

Lower Bound

The lower bound is an estimate of the minimum possible solution value. In the 0/1 Knapsack Problem, the lower bound can be calculated using the following formula:

LB = 0

Branching

The branching step involves creating new subproblems by fixing the value of one or more variables. In the 0/1 Knapsack Problem, we can branch on each item, creating two subproblems:

• Include item i in the knapsack (x_i = 1)
• Exclude item i from the knapsack (x_i = 0)

Bounding

The bounding step involves calculating the upper and lower bounds for each subproblem. If the upper bound is less than or equal to the lower bound, the subproblem can be pruned, as it cannot have a better solution than the current best solution.

Fathoming

The fathoming step involves checking if a subproblem has a feasible solution. If the subproblem has a feasible solution, it is added to the solution pool.

Implementation in C++

Here is an example implementation of the Branch and Bound algorithm for the 0/1 Knapsack Problem in C++:

#include 
#include 
#include 

using namespace std;

struct Item {
    int weight;
    int value;
};

bool compareItems(Item a, Item b) {
    return a.value / a.weight > b.value / b.weight;
}

int branchAndBound(vector items, int W, int idx, int value, int weight) {
    if (idx == items.size()) {
        if (weight <= W) {
            return value;
        } else {
            return -1;
        }
    }

    int includeValue = branchAndBound(items, W, idx + 1, value + items[idx].value, weight + items[idx].weight);
    int excludeValue = branchAndBound(items, W, idx + 1, value, weight);

    if (includeValue > excludeValue) {
        return includeValue;
    } else {
        return excludeValue;
    }
}

int main() {
    vector items = {{10, 60}, {20, 100}, {30, 120}, {40, 150}, {50, 200}};
    int W = 100;

    sort(items.begin(), items.end(), compareItems);

    int maxValue = branchAndBound(items, W, 0, 0, 0);

    cout << "Maximum value: " << maxValue << endl;

    return 0;
}

Conclusion

In this article, we discussed how to solve the 0/1 Knapsack Problem using the Branch and Bound algorithm in C++. The Branch and Bound algorithm is a powerful technique for solving optimization problems, and it can be applied to a wide range of problems. The implementation provided in this article can be used as a starting point for solving more complex variants of the 0/1 Knapsack Problem.