title: Implementing branch and bound for knapsack
body: <p>I'm having a headache implementing <a href="http://books.google.com/books?id=DAorddWEgl0C&amp;lpg=PA233&amp;pg=PA239#v=onepage&amp;q&amp;f=true" rel="nofollow">this (awful) pseudo-java code</a> (I wonder: why the hell people do that?) for the b&amp;b knapsack problem. This is my implementation so far, which  outputs a maximum of 80 (when it should print 90, for the items on the textbook sample). I created a Comparator (on a LinkedList) to sort the elements by Pi/Wi before passing them to the algorithm, but on this input is already presorted. I'm debugging right now (and updating the posted code), cause I guess it's an array indexing problem... or is there a mistake on the bounding function?</p>
  
  <p>input:</p>
  
  <pre><code>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&lt;Item&gt; items, int W) {
          int n = items.size();
  
          int [] p= new int[n];
          int [] w= new int[n];
  
          for (int i=0; i&lt;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 &lt;Node&gt; Q = new LinkedList&lt;Node&gt;();
  
          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&lt;=W &amp;&amp; u.profit&gt;maxProfit){
                  maxProfit = u.profit;
              }
  
              if(bound&gt;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&gt;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&gt;=W)
              return 0;
          else {
              result = u.profit;
              j= u.level +1;
              totWeight = u.weight;
  
              while ((j &lt; n) &amp;&amp; (totWeight + w[j]&lt;=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&lt;n)
                  result = result + (W-totWeight) * p[k]/w[k];// grab fraction of kth item
  
              return result;
          }
      }
  }
  </code></pre>