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

Suzhoumeite

5 min read

·

Jul 17, 2024

55

Share

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

Introduction

The 0/1 Knapsack Problem is a classic problem in computer science and operations research that involves finding the optimal solution to a problem of maximizing the value of items in a knapsack without exceeding its capacity. The problem is a combinatorial optimization problem, and its solution involves finding the best combination of items to include in the knapsack to maximize the total value while not exceeding the knapsack's capacity.

Formulation of the Problem

The 0/1 Knapsack Problem can be formulated as follows:

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's capacity.

Constraints:

• 0-1 constraint: Each item can be included only once in the knapsack.
• Capacity constraint: The total weight of the items included in the knapsack cannot exceed the knapsack's capacity W.

Branch and Bound Algorithm

The Branch and Bound Algorithm is a popular algorithm used to solve the 0/1 Knapsack Problem. The algorithm works by recursively exploring the solution space and bounding the optimal solution using upper and lower bounds.

Pseudocode of the Branch and Bound Algorithm

function branch_and_bound(items, W, v, w, n) {
  // Initialize the best solution and its value
  best_solution = {};
  best_value = 0;

  // Recursive function to explore the solution space
  function explore(i, weight, value, solution) {
    // If the current solution is better than the best solution, update it
    if (value > best_value) {
      best_solution = solution;
      best_value = value;
    }

    // If the current weight exceeds the knapsack's capacity, return
    if (weight > W) {
      return;
    }

    // Recursively explore the solution space
    for (j = i; j < n; j++) {
      // Calculate the new weight and value if item j is included
      new_weight = weight + w[j];
      new_value = value + v[j];

      // If the new weight does not exceed the knapsack's capacity, explore
      if (new_weight <= W) {
        explore(j + 1, new_weight, new_value, solution + [j]);
      }
    }
  }

  // Start the exploration from the first item
  explore(0, 0, 0, []);

  return best_solution;
}

Implementation in C++

Here is the implementation of the Branch and Bound Algorithm in C++:

#include 
#include 
#include 

using namespace std;

struct Item {
  int value;
  int weight;
};

int branch_and_bound(vector items, int W) {
  int n = items.size();
  int best_value = 0;
  vector best_solution;

  function)> explore =  {
    if (value > best_value) {
      best_value = value;
      best_solution = solution;
    }

    if (weight > W) {
      return;
    }

    for (int j = i; j < n; j++) {
      int new_weight = weight + items[j].weight;
      int new_value = value + items[j].value;

      if (new_weight <= W) {
        explore(j + 1, new_weight, new_value, solution + [j]);
      }
    }
  };

  explore(0, 0, 0, {});

  return best_value;
}

int main() {
  int W = 50; // Knapsack capacity
  vector items = {{10, 20}, {20, 30}, {30, 40}, {40, 50}, {50, 60}};

  int best_value = branch_and_bound(items, W);
  cout << "Best value: " << best_value << endl;

  return 0;
}

Conclusion

In this article, we have discussed the 0/1 Knapsack Problem and its solution using the Branch and Bound Algorithm. We have also implemented the algorithm in C++. The Branch and Bound Algorithm is a powerful tool for solving combinatorial optimization problems like the 0/1 Knapsack Problem.