a675: 00166 - Making Change
Tags : DP Greedy 找零問題 有限背包
Accepted rate : 50人/51人 ( 98% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-03-16 22:34

Content

我們知道假設我們有無限多的各式硬幣時,我們可以有很多種方式組合出特定的金額。瘋狂的電腦科學家們於是稍微把這個問題複雜化,現在考慮我們買東西付錢時,我們不可能隨身攜帶無限多的各式硬幣,在這種情況下,可以組成特定金額的方式就會被我們身上現有的硬幣所限制。

瘋狂的電腦科學家們好奇的是,假設店家手上有足夠的硬幣可以找錢,在這次交易中,我們付出去與店家找回來所使用的硬幣總數,最小可以是多少。(在這個問題中我們以紐西蘭的硬幣為例,共有:5c、10c、20c、50c$1、$2這六種硬幣,不考慮紙鈔)

舉例來說,如果我們買了一個55c的物品,而且手上不幸剛好沒有50c的硬幣,所以一種可能的付法就是給店家2*20c + 10c + 5c,這麼一來這次交易中總共就有四枚硬幣被使用到;如果我們選擇付$1給店家,那麼店家要找回45c,這麼一來總共還是需要用到四枚硬幣;但是,如果我們給店家$1 + 5c,則店家只需要找回50c,這樣就只需要用到三枚硬幣,這就是這次交易中,所使用的最小硬幣總數。

你的任務就是,寫個程式讀入我們有多少硬幣在手上、以及要付多少錢給店家,並找出所使用的最小硬幣總數。

Input

輸入會包含許多行,一行代表一次交易。每一行的六個整數代表前面提到的六種硬幣我們手上各有多少個(分別對應到面提到的順序:5c、10c、20c、50c、$1、$2),該行的最後一個數字會是一個小於五的實數,代表這次交易中要付多少錢。當程式讀到六個零時(0 0 0 0 0 0),代表測資結束。

測資不會出現手上的零錢無法或不足以支付交易金額的情形,也就是說交易金額永遠是5c的倍數。

Output

對每一行測試資料,輸出一行包含最小被使用的硬幣總數。輸出長度為3,靠右對齊。請參考Sample Output。

Sample Input #1
2 4 2 2 1 0  0.95
2 4 2 0 1 0  0.55
0 0 0 0 0 0
Sample Output #1
  2
  3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :

Lucky貓 ★★★  

Tags:
DP Greedy 找零問題 有限背包
出處:
UVa166 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」