Ruby每周一测 - 找零钱

这个有bug，如38, [20, 19, 1]

目前看起来还是老庄的比较好，但MS效率不高

最好有人评论，不然就没有意义了。

一个测效率例子
380,[20, 19, 1]
老庄的估计要跑数十秒吧
femto我等了一段时间没等下去
官方解法跑是ms单位的

这个SCIP里面有一个一样的题目的

这么夸张？我测试怎么才不到1秒？

抱歉，是我搞错了，因为加了打印，不加的话接近1s吧

25，10，5，1看成5进制试试

  首先，此类问题，从代码的可读性，可维护性出发，老庄的递归算法无容置疑是最优的。当然，是以牺牲效率为前提，我测试了下，用老庄的算法跑380,[20, 19, 1]，大概运行时间是1秒左右。
  如果以效率优先的话，那肯定需要将递归算法非递归化。这里我给一个十分土的方法：
  我先假设如果有找零的方案的话，零钱的个数不大于50（50*20也有10刀了，应该是不小的零钱数量吧，呵呵），算法思想无非是穷举加上回退操作。简单描述如下：首先拿出一个最大的零钱给客户（当然，存在的话），然后再取一个最大的零钱（合理的），。。。以此类推。。当某一次取操作，发现不成功时，则叫客户把你上次给他的钱退回，然后换一个次大的零钱。。。以此类推。。。这样得到的方案肯定是最优的，而且不采用递归，效率能得到很大的提升。不多解释，上详细代码：

make_change_code = ""
50.times do|index|
  make_change_code = <<EOS
  coins.each do |value_#{index}|
    if value_#{index} <= amount
      result.push(value_#{index})
      amount -= value_#{index}
    else
      next
    end
    throw :done if amount == 0
    #{make_change_code}
    result.pop
    amount += value_#{index}
  end
EOS
end

make_change_code = <<EOS
def make_change(amount, coins = [25, 10, 5, 1])
  result = []
  catch :done do
  #{make_change_code}
  end
  result
end
EOS

instance_eval(make_change_code)
require 'benchmark'

result = []
Benchmark.bm do |bm|
  bm.report("benchmark") do
    result = make_change(380, [20, 19, 1])
  end
end
p result

    benchmark的结果是（我没有把instance_eval的消耗计算进来）：
                        user         system      total                real
benchmark  0.047000   0.000000   0.047000   (  0.016000)
 
  之所以土，是因为我动态生成make_change方法时，写死了最大零钱数（50个），不是很灵活（似乎也足以应付一般情况，除非哪个家伙搞张大票子来换零钱砸人玩。呵呵）。
  如果要不土的话，其实思路也差不多。。。搞一栈，找一个最大合理零钱丢进去，然后继续找，多设几个表示器，发现选择不合理，则执行出栈操作，并设置相应标志位。。。具体代码没写，大致如此吧。。。
  PS：上面的代码没有详细测试，不知道bug情况如何。

  另外，如果考虑现实生活中的例子，有1分的零钱的话，下面这个方案似乎也可行

class Array
  def find_first
    each do|value|
      return value if yield value
    end
  end
end

require 'benchmark'

def make_change(amount, coins = [25, 10, 5, 1])
  result = []
  loop do
    break if amount == 0
    one_coin = coins.find_first{|value| value<=amount}
    result << one_coin
    amount -= one_coin
  end
  result
end  

result = []
Benchmark.bm do |bm|
  bm.report("benchmark") do
    result = make_change(39)
  end
end
p result

 

 

to:woody_420420
有bug

make_change(14, [10, 7, 1])  ==> [10,1,1,1,1]

正确结果是：[7,7]