Branch and Bound Knapsack Java

Question

import java.io.*;
import java.util.*;

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

public class KnapsackBB{
        public static void main(String args[])throws Exception{
                int maxProfit;
                int N;
                int W;
                int wt;
                int vl;
                int maxVal;

                Scanner input = new Scanner(System.in);

                System.out.println("Please enter the number of items: ");
                N = input.nextInt();
                System.out.println("Please enter the capacity of the Knapsack: ");
                W = input.nextInt();

                int[] Vl = new int[N];
                int[] Wt = new int[N];

                for(int i = 0; i < N; i++){
                        System.out.println("Please enter the weight anc value of item " + i + ": ");
                        wt = input.nextInt();
                        vl = input.nextInt();

                        Wt[i] = wt;
                        Vl[i] = vl;
                }


                //for(int i  = 0; i < 1000; i++){
                        maxVal = knapsack(N, Vl, Wt, W);
                //}

                System.out.println(maxVal);

        }


        public static int bound(node u, int n, int W, int[] pVa, 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;
                }
        }

        public static int knapsack(int n, int[] p, int[] w, int W){
                Queue<node> Q = new LinkedList<node>();
                node u = new node();
                node v = new node();
                int[] pV = new int[p.length];
                int[] wV = new int[w.length];
                Q.poll();

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

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

                int maxProfit = 0;

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

                while (Q.size() > 0){
                        v = Q.remove();

                        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.add(u);
                        }

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

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

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

                }
                return maxProfit;
        }
}

I am having a problem with my program in that I am getting the wrong output. I have converted from C++ from another program I have found online and it works correctly.

Input:

4

6

2 10

3 12

4 5

3 15

Output should be:

22

Output obtained:

12

Answer 1

Your copying skills leave much to be wanted - and it would have been helpful if you had added a link to the original source.

It seems that you have added the lines

u.weight = v.weight;
u.profit = v.profit;
u.bound = bound(u, n, W, pV, wV);
if (u.bound > maxProfit){
    Q.add(u);
}

twice. At least that provides the "22" answer you were looking for.

That said, the solution is far from Object Oriented, and Java style in general.