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.
