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.

## No comments:

Post a Comment