## Friday, November 14, 2008

`object Solver {    def cache = new scala.collection.mutable.HashMap[(List[Int], Int), List[List[Int]]]()    /**     * Generates a list of solutions to the Diophantine inequality     * w1*x1 + w2*x2 +... wN*xN >= max     * where weights = (w1,w2,...wN)     * Each solution is a minimal solution.     * This means that if (x1,x2,...xN) is a solution     * then (x1,x2, ... ,-1 + xM , ... xN) is NOT a solution     */    def solve(weights: List[Int], max: Int): List[List[Int]] = {        if (cache.contains((weights,max))){          return cache((weights,max))        }        if (weights.length == 1) {            return List(List(max / weights(0) + 1))        }        var all: List[List[Int]] = Nil        var a = 0        while (a * weights(0) < max) {            all = all ++ solve(weights.drop(1).toList, max - a * weights(0)).map(a :: _)            a += 1        }        val solution = (a :: weights.drop(1).map(_ * 0)) :: all        cache.put((weights,max), solution)        solution    }    /**     * For a given set of weights (w1, w2, ... wN) and costs (c1, c2, ... cN)     * This finds the solution (x1,x2,...xN) to the inequality     * w1*x1 + w2*x2 + ... wN*xN <= max that minimizes the total cost     * c1*x1 + c2*x2 + ... cN*xN     * It returns the solutions as a Tuple where the first element is     * the solution (x1,x2,...xN) and the second is the minimal total cost     */    def optimizer(costs: List[Int], weights: List[Int], max: Int): (List[Int], Int) = {        val solutions = solve(weights, max)        var answer: List[Int] = Nil        var best = (answer, Integer.MAX_VALUE)        solutions.foreach((solution) => {            val cost = solution.zip(costs).foldLeft(0){(a,b) => a + b._1*b._2}            if (cost < best._2) {                best = (solution, cost)            }              })        best    }}`