/**
   * Method to find an optimal solution to KNAPSACK problem, given:
   * - s, indexed array of the sizes
   * - w, index array of element worth (profit) 
   * - indexes of s and w are sorted by w[i]/s[i] values
   * - size, the total size constraint
   * It returns an external-node Configuration object for optimal solution.
   */
  public static Configuration solve(int[] s, int[] w, long size) {
    /* Create priority queue for selecting current best configurations */
    PriorityQueue p = DoublePriorityQueue();
    /* Create root configuration */
    Configuration root = new Configuration(s,w,size);
    double upper = root.getUpperBound(); // upper bound for root
    Configuration curBest = root;  // the current best solution
    p.insertItem(new Double(-upper), root);  // add root configuration to p
    /* generate new configurations until all viable solutions are found */
    while (!p.isEmpty()) {
      double curBound = -((Double)p.minKey()).doubleValue(); // we want max
      Configuration curConfig = (Configuration) p.removeMin();
      if (curConfig.getIndex() >= s.length-1) continue; // nothing to expand
      /* Expand this configuration to include the next item */
      Configuration child = curConfig.expandWithNext();
      /* Test if new child has best valid worth seen so far */
      if ((child.getWorth() > curBest.getWorth()) && (child.getSize() <= size)) 
        curBest = child;
      /* Test if new child is worth expanding further */
      double newBound = child.getUpperBound();
      if (newBound > curBest.getWorth()) 
        p.insertItem( new Double(-newBound), child);
      /* Expand the current configuration to exclude the next item */
      child = curConfig.expandWithoutNext();
      /* Test if new child is worth expanding further */
      newBound = child.getUpperBound();
      if (newBound > curBest.getWorth()) 
        p.insertItem( new Double(-newBound), child);
    }
    return curBest;
  }