Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package lessmoney
- import scala.annotation.tailrec
- import scala.util.control.Breaks._
- /**
- * Created by almightykim on 7/10/15.
- */
- object LessMoney extends App {
- @tailrec
- def findMaxDemon(ncoins:Int, value:Int, dnoms:Set[Int]) : (Int, Set[Int]) = {
- val usable = dnoms.filter(_<= value)
- if (usable.isEmpty){
- return (value, Set.empty[Int])
- }
- val md = usable.max
- val mq = (value.toDouble / md.toDouble).toInt
- val nc = if (ncoins < mq) ncoins else mq
- val rem = value - (nc * md)
- val rd = dnoms -- Set(md)
- if (rem == 0 || rd.isEmpty){
- return (rem, rd)
- }
- findMaxDemon(ncoins, rem, rd)
- }
- def rems(ncoin:Int, value:Int, dnoms:Set[Int]) : Set[Int] = {
- (1 to value).reverse.map{ v =>
- val (rem, rd) = findMaxDemon(ncoin, v, dnoms)
- rem
- }.filter{ r =>
- r != 0
- }.toSet
- }
- def findMaxSet(ncoin:Int, value:Int, dnoms:Set[Int], prs:Set[Int]) : Set[Int] = {
- var nmind = 0
- var pprs = prs
- for(d <- 1 to value){
- if (!dnoms.contains(d)){
- val rs = rems(ncoin, value, dnoms ++ Set[Int](d))
- if (rs.isEmpty) {
- println("We've found an optimal set")
- return dnoms ++ Set(d)
- }
- if (rs.size <= pprs.size ){
- nmind = d
- pprs = rs
- println(s"nmind:$nmind rs:$rs")
- }
- }
- }
- val ndnoms = dnoms ++ Set(nmind)
- //println(s"ncoin:$ncoin, value:$value, dmons:$ndnoms, prs:$pprs")
- findMaxSet(ncoin, value, ndnoms, pprs)
- }
- def minCoinage(ncoin:Int, value:Int, dnoms:Set[Int]) : Int = {
- val rs = rems(ncoin, value, dnoms)
- if (rs.isEmpty){
- return 0
- }
- val ndnoms = findMaxSet(ncoin, value, dnoms,rs)
- (ndnoms -- dnoms).size
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement