//package teneyck.backtrackstuff;
import java.util.*;

public class KnapsackBandB {
  private double maxValue;
  private double K;   //capacity 
  private double [ ] s;
  private double [ ] v;
  private Vector bestList;
  private int numItems;
  private Queue q;
  
  class Node {
    int level;
    double size, value, bound;
    Vector contains;
    protected Node( ) {
      level = 0;
      size = 0.0;
      value = 0.0;
      bound = 0.0;
      contains = null;
    }
    protected void copyList(Vector v) {
      if (v == null || v.isEmpty( ) )
        contains = new Vector( );
      else
        contains = new Vector(v);
    }
    protected void add(int index) {
      contains.add(new Integer(index) );
    }
  }  
  
  public KnapsackBandB(double capacity, double [ ] size, double [ ] value,int n) {
    maxValue = 0.0;
    K = capacity;
    s = size;
    v = value;
    numItems = n;
    bestList = null;
    q = new Queue( );
  }
  
  private void knapsack( ) {
    while (!q.isEmpty( ) ) {
      Node temp = (Node)q.dequeue( );
      if (temp.bound > maxValue) {
        Node u = new Node( );
        u.level = temp.level+1;
        u.size = temp.size + s[temp.level+1];
        u.value = temp.value + v[temp.level+1];
        u.copyList(temp.contains);
        u.add(u.level);
        if (u.size < K && u.value > maxValue) {
          maxValue = u.value;
          bestList = new Vector(u.contains);
        }
        u.bound = bound(u.level, u.size, u.value);
        if (u.bound > maxValue)
          q.enqueue(u);
        Node w = new Node( );
        w.level = temp.level+1;
        w.size = temp.size;
        w.value = temp.value;
        w.bound = bound(w.level, w.size, w.value);
        w.copyList(temp.contains);
        if (w.bound > maxValue)
          q.enqueue(w);
      }
    }
  }
  
  private double bound(int item, double size, double value) {
    double bound = value;
    int k = item + 1;
    double totalSize = size;
    if (totalSize > K) return 0.0;
    while (k < numItems && totalSize + s[k] < K) {
      totalSize += s[k];
      bound += v[k];
      k++;
    }
    if (k < numItems)
      bound += (K - totalSize) * (v[k]/s[k]);
    return bound; 
  }
  
  public void findSolution ( ) {
    Node root = new Node( );
    root.level = 0;
    root.size = 0.0;
    root.value = 0.0;
    root.bound = bound(0, 0.0, 0.0);
    root.copyList( null);
    q.enqueue(root);
    knapsack( );
    System.out.print("The solution set is: ");
    for (int i = 0; i < bestList.size( ); i++) {
      System.out.print("  "+bestList.get(i));
    }
    System.out.println( );
    System.out.println("The value contained is: $ "+ maxValue);
  }
  public static void main(String [ ] args) {
    double [ ] sizes = {0.0, 3.0, 5.0, 9.0, 5.0};
    double [ ] values = {0.0, 45.0, 30.0, 45.0, 10.0};
    KnapsackBandB nappy = new KnapsackBandB(16.0, sizes, values, 5);
    nappy.findSolution( );
  }
      
      
}