suzhoumeite.com
Home

0/1 Knapsack Problem Using Branch And Bound Code In Java

6 min read Jul 17, 2024
0/1 Knapsack Problem Using Branch And Bound Code In Java

0/1 Knapsack Problem using Branch and Bound: A Java Implementation

Introduction

The 0/1 Knapsack Problem is a classic problem in combinatorial optimization. It involves finding the optimal subset of items to include in a knapsack of limited capacity, such that the total value of the selected items is maximized. In this article, we will implement the Branch and Bound algorithm to solve the 0/1 Knapsack Problem in Java.

Problem Statement

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

Given:

  • A set of n items, each with a weight w_i and a value v_i
  • A knapsack with a capacity W
  • A binary decision variable x_i indicating whether item i is included in the knapsack (1) or not (0)

Objective: Maximize the total value of the selected items, subject to the constraint that the total weight of the selected items does not exceed the knapsack capacity:

Maximize: ∑(v_i * x_i) Subject to: ∑(w_i * x_i) ≤ W x_i ∈ {0, 1} for i = 1, 2, ..., n

Branch and Bound Algorithm

The Branch and Bound algorithm is a popular method for solving integer programming problems like the 0/1 Knapsack Problem. The algorithm works by recursively exploring the feasible region of the problem, using a combination of branching and bounding techniques to prune the search space.

Here is the high-level outline of the algorithm:

  1. Initialize: Set the upper bound (UB) to infinity, and the lower bound (LB) to zero.
  2. Branch: Select a node from the search tree, and branch on it by generating two child nodes: one with the selected item included, and one with the selected item excluded.
  3. Bound: Calculate the upper bound (UB) for each child node using a bounding function.
  4. Prune: Discard any child nodes with a UB less than or equal to the current LB.
  5. Repeat: Recursively apply steps 2-4 until the search tree is exhausted or the optimal solution is found.

Java Implementation

Here is a Java implementation of the Branch and Bound algorithm for the 0/1 Knapsack Problem:

public class KnapsackProblem {
    int n; // number of items
    int W; // knapsack capacity
    int[] w; // item weights
    int[] v; // item values
    int[] x; // binary decision variables

    public KnapsackProblem(int n, int W, int[] w, int[] v) {
        this.n = n;
        this.W = W;
        this.w = w;
        this.v = v;
        this.x = new int[n];
    }

    public int solve() {
        int LB = 0; // lower bound
        int UB = Integer.MAX_VALUE; // upper bound
        Node root = new Node(0, 0, new int[n]); // root node
        Node bestNode = null;

        while (true) {
            Node node = selectNode(root);
            if (node == null) break;

            int value = calculateValue(node);
            if (value > LB) {
                LB = value;
                bestNode = node;
            }

            int bound = calculateBound(node);
            if (bound <= LB) {
                // prune node
                continue;
            }

            // branch on node
            Node leftChild = new Node(node.level + 1, node.weight + w[node.level], node.x.clone());
            leftChild.x[node.level] = 1;

            Node rightChild = new Node(node.level + 1, node.weight, node.x.clone());
            rightChild.x[node.level] = 0;

            root.children.add(leftChild);
            root.children.add(rightChild);
        }

        return LB;
    }

    private int calculateValue(Node node) {
        int value = 0;
        for (int i = 0; i < node.level; i++) {
            if (node.x[i] == 1) value += v[i];
        }
        return value;
    }

    private int calculateBound(Node node) {
        int remainingWeight = W - node.weight;
        int value = calculateValue(node);

        for (int i = node.level; i < n; i++) {
            if (remainingWeight >= w[i]) {
                value += v[i];
                remainingWeight -= w[i];
            } else {
                value += (remainingWeight * v[i]) / w[i];
                break;
            }
        }

        return value;
    }

    private Node selectNode(Node node) {
        // select the node with the highest upper bound
        Node bestChild

Featured Posts