def make_change(money, coins)
dp = [0]
path = []
result = {}
coins.each_with_index do |coin, index|
coin.upto(money) do |i|
if !dp[i - coin].nil? && (dp[i].nil? || dp[i - coin] + 1 < dp[i])
dp[i] = dp[i - coin] + 1
coins[index] += 1
path[i] = i - coin
end
end
end
if path[money].nil?
puts "impossible." and return
end
i = money
loop do
break if path[i].nil?
result[i - path[i]] ||= 0
result[i - path[i]] += 1
i = path[i]
end
p result # 具体解
end
make_change(102135, [10000, 100, 1])
# => {1=>35, 100=>21, 10000=>10}
简单做。从额数最大的金开始处理,先整除,再模除,金银铜依次处理。输出的时候判断再做个判断,代码如下:
很简单的写了一个。
嗯...不知道计算速度快 还是字符串截取速度快
结果: 10金币21铜币35银币
function change($number){
关注微信公众号php技术大全:phpgod,精彩分享每日不断。