Implementation of branches and frames for a satchel

Question

I have a headache implementing this (terrible) pseudo-java code (I wonder: why the hell do people do this?) For the b & b knackack problem. This is my implementation so far, which displays a maximum of 80 (when it should print 90, for elements on a sample textbook). I created a Comparator (by LinkedList) to sort items by Pi / Wi before passing them to the algorithm, but this input is already preceded. I am debugging right now (and updating the published code) because I assume this is a problem of indexing the array ... or is there an error in the bounding function?

input:

4 16 //# items maxWeight 40 2 // profit weight 30 5 50 10 10 5 class Node { int level; int profit; int weight; double bound; } public class BranchAndBound { static int branchAndBound (LinkedList<Item> items, int W) { int n = items.size(); int [] p= new int[n]; int [] w= new int[n]; for (int i=0; i<n;i++){ p [i]= (int)items.get(i).value; w [i]= (int)items.get(i).weight; } Node u = new Node(); Node v = new Node(); // tree root int maxProfit=0; LinkedList <Node> Q = new LinkedList<Node>(); v.level=-1; v.profit=0; v.weight=0; // v initialized to -1, dummy root Q.offer(v); // place the dummy at the root while(!Q.isEmpty()){ v = Q.poll(); if (v.level==-1){ u.level=0; } else if(v.level != (n - 1)) { u.level = v.level+1; // set u to be a child of v } u = new Node(); u.weight = v.weight + w[u.level];// set u to the child u.profit = v.profit + p[u.level]; // that includes the //next item double bound = bound(u, W, n, w, p); u.bound=bound; if(u.weight<=W && u.profit>maxProfit){ maxProfit = u.profit; } if(bound>maxProfit){ Q.add(u); } u = new Node(); u.weight = v.weight; // set u to the child that u.profit = v.profit;// does NOT include the next item bound = bound(u, W, n, w, p); u.bound = bound; if (bound>maxProfit){ Q.add(u); } } return maxProfit; } public static float bound(Node u, int W, int n, int [] w, int [] p){ int j=0; int k=0; int totWeight=0; float result=0; if(u.weight>=W) return 0; else { result = u.profit; j= u.level +1; totWeight = u.weight; while ((j < n) && (totWeight + w[j]<=W)){ totWeight = totWeight + w[j]; // grab as many items as possible result = result + p[j]; j++; } k=j; // use k for consistency with formula in text if (k<n) result = result + (W-totWeight) * p[k]/w[k];// grab fraction of kth item return result; } } } 

Answer 1

I only tested it with this example, but it looks like the pseudo-code says

 enqueue(Q, u) 

you should add a copy of u to the linked list, instead of passing the link to u and continuing to manipulate it.

In other words, define a copy constructor for the class Node and do

 Q.offer(new Node(u)); 

instead

 Q.offer(u); 

In fact, the above code only allocates two instances of the Node class for calling branchAndBound(..)