/*
 * example Knapsack-problem solver code
 * 
 * to show an example of _dynamic programming_ 
 */

import java.util.Arrays;

public class Knapsack {

  /**
   * data members we'll use
   */
  private int[] value;  // the list of values (input)
  private int[] weight; // the list of weights (input)
  
  private int[] bestValue;  // the table of best values (per weight)
  

  /**
   * constructor for an instance of the Knapsack problem
   * @param values_input, the list of values
   * @param weights_input, the list of weights
   */
  public Knapsack(int[] values_input, int[] weights_input) {
    this.value = values_input;
    this.weight = weights_input;
    
    this.bestValue = null;  // don't know the size yet...
  }
  
  
  /**
   * max_value returns the greatest (candy-)value we can obtain
   *           for a particular capacity
   * @param cap, the capacity of our knapsack
   * @return the maximum (candy-)value for cap capacity
   */
  public int max_value(int cap) {
    // if we haven't computed the table, do so!
    if (this.bestValue == null || this.bestValue.length < (cap+1))
      compute_knapsack(cap);
    
    // return the value requested
    return this.bestValue[cap];
  }
  
  
  /**
   * compute_knapsack creates and fills the dynamic programming
   *                  table of best values
   * @param cap, the capacity of the knapsack and the value up to
   *        which we compute the table of best values
   */
  private void compute_knapsack(int cap) {
    this.bestValue = new int[cap+1];     // create the table to fill in
    
    // fill in the "base case" (at 0)
    this.bestValue[0] = 0;               // no capacity, no value!
    
    int num_items = this.weight.length;  // the number of items
    // fill in the table _after_ 0
    for (int c=1 ; c<=cap ; c++) {       // Look, it's c++!
      int best = this.bestValue[c-1];  // loseit case
      for (int n=0; n<num_items ; ++n) 
      {
        int reach_back_index = c - this.weight[n];  // useit cases
        if (reach_back_index >= 0) 
        {   // only look at feasible possibilities
            int val = this.bestValue[reach_back_index] + this.value[n];
            if (val > best) 
              best = val;
        }
      }
      // put the best value in the table
      this.bestValue[c] = best;
    }
    System.out.println("this.bestValue is " + Arrays.toString( this.bestValue ));
    return;
  }
  
  /**
   * main, for testing small problem cases out...
   * @param args, command-line parameters (not used)
   */
  public static void main(String[] args) {
    int[] values_in  = { 100, 120, 230, 560, 675 };
    int[] weights_in = { 2, 3, 5, 7, 9 };
    
    Knapsack Knap_in_class = new Knapsack( values_in, weights_in );
    int best13 = Knap_in_class.max_value(13);
    System.out.println("Best value for cap of 13: " + best13); // 875
    
    int best14 = Knap_in_class.max_value(14);
    System.out.println("Best value for cap of 14: " + best14); // 1120
    
    int best42 = Knap_in_class.max_value(42);
    System.out.println("Best value for cap of 42: " + best42); // 3360
  }
  
  
  
}