Facebook Puzzler in Scala

An associate of mine pointed out some fun programming puzzles on Facebook. This one was interesting to me. It was interesting because I think it is poorly. Well at the very least it confused on first read. When specifying the cost/weight, if they would have just used the word 'each' in there it would have been far less confusing... Anyways, I decided to solve the problem in Scala, since I've been doing a lot more Scala programming lately. Here is my Solver:

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
    }
}

I put in the cache for memoization purposes, but it doesn't always help. For example, with their sample input/output, the cache is useless. Anyways, I showed the problem to other smarter folks who immediately pointed out that this was a variant of the unbounded knapsack problem and that my solution uses dynamic programming.

Here's a dirty little secret about yours truly. I studied mathematics in college, not computer science. So it's always amusing for me to come across a problem like this and have people start talking about CS terms. Personally I looked it as a Diophantine equation (inequality to be more accurate.) Of course maybe if I was a CS person, then I would have written a nicer solution.