作者markmcm (Markmcm)
看板Ruby
标题[心得] 换零钱问题
时间Wed Apr 27 10:42:06 2011
再次献丑了，这是换零钱的问题的练习：
amounts = ARGV.map(&:to_i)
levels = [1000,500,100,50,10,5,1]
levels.each {|level| printf("%4d,",level)}
print("\n")
amounts.each do |amount|
levels.each do |level|
q=0
if(level <= amount)
q,amount = amount.divmod level
end
printf("%4d,",q)
end
print("\n")
end
一次输入一连串的数字，能够列出每串数字需要的硬币数
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 163.29.185.99
1F：→ SansWord:这只是换出等价零钱吗？还是也有个数最少? 04/27 13:39
2F：→ markmcm:每个币值都是大的币值的因数所以用greedy也会是最小值吧 04/27 15:00
3F：推 SansWord:不对喔，换零钱问题不是greedy 05/02 12:01
4F：→ SansWord:假设今天有5,4,2,1 四种币值，要换8元，用Greedy会错 05/02 12:01
5F：→ SansWord:喔对，markmcm您说的是对的。 05/02 12:02
做了个用动态规划的函数，现在用 5,4,2,1 来换 8 就没问题了
amounts = ARGV.map(&:to_i)
$denominations = [5,4,2,1]
def change(amount)
min_number = [0] #min coin count for [index] amount
min_first_element = [] #first element of min coin set for [index] amount
for p in 1..amount
min_coin = amount #amount is the max coins changes
coin = nil
$denominations.find_all{|i| i<=p}.each{|denomination|
if (1+min_number[p-denomination]) <= min_coin
min_coin = 1+min_number[p-denomination]
coin = denomination
end
}
min_number[p] = min_coin
min_first_element[p] = coin
end
a = amount
for i in 1..min_number[amount]
printf("%4d,",min_first_element[a])
a -= min_first_element[a]
end
end
※ 编辑: markmcm 来自: 163.29.185.99 (05/05 16:16)