lab10

/**
 * lab10: starter code
 *
 * A Rod is constructed from an array of non-negative prices, where
 * price[i] represents the selling price of a rod of length i. We
 * assume here that price[0] is 0.
 *
 * We wish to determine the maximum profit obtainable by cutting up a
 * rod of length n and selling the pieces. We also wish to know the
 * lengths of each cut segment that obtains the maximum profit. Thus,
 * a Result consists of two pieces of information: the total profit
 * and a list of lengths.
 *
 * TODO:
 *
 * (1) Create a lab10 project in IntelliJ and copy your code for Map,
 * HashMap, AList, Assoc, and DoublyLinkedList from p4 into the src
 * directory.
 *
 * (2) Implement the naive brute-force solution, as described in
 * lecture, to generate all configurations of different pieces and
 * find the highest priced configuration. Do this in two stages:
 *
 *     -- Implement the basicCut() method to return an int
 *        representing the maximal profit.
 *
 *     -- Implement the fancyCut() method to return a Result
 *        object that includes the maximal profit and a list
 *        of corresponding rod lengths
 *
 * (3) Memoize your fancyCut() method by using a cache (of type
 * HashMap) as an instance variable.
 *
 * @author Colin Curry & Adam Hilinski
 *
 */

public class Rod {

  class Result {
    int profit;
    List<Integer> lengths;

    Result(int profit) {
      this.profit = profit;
      lengths = new DoublyLinkedList<>();
    }

    public String toString() {
      return String.format("[numCuts=%d, profit=%d, lengths=%s]",
                           lengths.size() - 1, profit, lengths);
    }
  }

  private int[] price;

  public Rod(int[] price) {
    this.price = price;
  }

  /**
   * TODO
   *
   * Returns the maximal profit obtainable by cutting a rod
   * of length n. Implemented as a top-down recursive method.
   * Runs in O(2^n) time.
   */

  public int basicCut(int n) {
    if(n == 0)
      return 0;
    int profit = Integer.MIN_VALUE;
    for(int i = 1; i <= n; i++) {
      profit = Math.max(profit, (price[i]) + basicCut(n - i));
    }
    return profit;
  }

  /**
   * TODO
   *
   * Returns a Result containing the maximal profit obtainable by
   * cutting a rod of length n and a list of corresponding rod
   * lengths. Implemented as a memoized top-down recursive method.
   * Runs in O(n^2) time.
   */

  public Result fancyCut(int n) {
    if(n == 0)
      return new Result(0);
    Result[] cache = new Result[n];

    int profit = 0;
    for(int i = 1; i <= n; i++) {
      if(profit < price[i]) {
        profit = ;
        cache[i] =
      }
    }

    return null;
  }

}