[心得] 換零錢問題

[markmcm (Markmcm)]

再次獻醜了，這是換零錢的問題的練習：

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
→ SansWord:這只是換出等價零錢嗎？還是也有個數最少?
→ markmcm:每個幣值都是大的幣值的因數所以用greedy也會是最小值吧
推 SansWord:不對喔，換零錢問題不是greedy
→ SansWord:假設今天有5,4,2,1 四種幣值，要換8元，用Greedy會錯
→ SansWord:喔對，markmcm您說的是對的。
做了個用動態規劃的函數，現在用 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)