Making Money with Gelar: coin changing

coin changing

More Coin Changers in Scala - Recursive, Memoized and Dynamic

greedy algorithms provide optimal solutions for some combinations of coin denominations, it does not offer correct optimal solution for all combinations. In fact, coin changing problem is a well discussed example of a dynamic programming algorithm that exhibits the optimal substructure property, where the optimal solution for the problem can be implemented in terms of optimal solutions of smaller subproblems.

One of the approaches to solving the problem is by defining the subproblems through a recurrence relation and implementing a top down recursive algorithm like the following :

object CoinChanger {
def changeRecursive(denominations: List[Int], amount: Int): (Int, List[Int]) = amount match {
case 0 => (0, List())
case a =>
val ch = ((java.lang.Integer.MAX_VALUE, List[Int](), 0) /: denominations)
{
(x, y) =>
if (amount >= y) {
lazy val ret = changeRecursive(denominations, amount - y)
if (ret._1 + 1 < x._1) {
(ret._1 + 1, ret._2, y)
} else x
} else x
}
(ch._1, ch._3 :: ch._2)
}
}

It is a top down approach of solving the problem but has the obvious drawback of naive recursive implementations. Same subproblems are being solved repeatedly, leading to an exponential complexity of O(M exp d) for computing the optimal combination for M amount with d denominations.
Using memoization, we can speed up the implementation significantly, while keeping the current top down approach. The following implementation uses the memo functions from Scalaz :

object CoinChanger {
def changeRecursiveMemoized(denominations: List[Int], amount: Int): (Int, List[Int]) = {
val m = arrayMemo[(Int, List[Int])](amount)
def change(a: Int): (Int, List[Int]) = a match {
case 0 => (0, List())
case x =>
val ch = ((java.lang.Integer.MAX_VALUE, List[Int](), 0) /: denominations)
{
(x, y) =>
if (a >= y) {
lazy val ret = m(change)(a - y);
if (ret._1 + 1 < x._1) {
(ret._1 + 1, ret._2, y)
} else x
} else x
}
(ch._1, ch._3 :: ch._2)
}
change(amount)
}
}


Problems that exhibit optimal substructure property have efficient dynamic programming solutions. However the subproblems have to be solved before, so as to use the precomputed results in solving the bigger problem. This implies a bottom up approach instead of the top dopwn approach that the above recursive algorithm implements. The following algorithm attempts to solve an apparently harder problem of finding out the optimal combination of changes for all amounts from 1 to the specified input amount. In the following dynamic programming implementation, we get the same result, but by changing the problem definition to one which uses the precomputed values from smaller subproblems more deterministically and efficiently. The algorithm has a complexity of O(Md) for computing the optimal combination for M amount with d denominations :

object DPCoinChanger {
def dpChange(denominations: List[Int], amount: Int) = {
var bestNumCoins = new Array[(Int, List[Int])](amount + 1)
bestNumCoins(0) = (0, List[Int]())
List.range(1, amount + 1).foreach{a =>
bestNumCoins(a) = (java.lang.Integer.MAX_VALUE, List())
denominations.foreach{d =>
if (a >= d) {
if (bestNumCoins(a - d)._1 + 1 < bestNumCoins(a)._1) {
bestNumCoins(a) = (bestNumCoins(a - d)._1, d :: bestNumCoins(a - d)._2)
}
}
}
}
bestNumCoins(amount)
}
}

SEMOGA berMANfAAt........

No comments:

Copyright © Making Money with Gelar Urang-kurai