[Java] UVa 10626 Buying Coke

題目連結

題意:
一瓶可樂 $8
每組題目給定要買幾瓶、1元、5元、10元硬幣數量
每次只能買一瓶，找錢會以最少的硬幣數量
求使用最少硬幣的買法，輸出使用硬幣總數

例如:
2 2 1 1
表示要買 2 瓶、$1, $5, $10 分別有 2, 1, 1 個
我們知道，用最少的買法就是花 1 個 $10
所以用 $10 買了一瓶後，會找 2 個 $1
此時硬幣數分別為 4, 1, 0
還有一瓶，只能用 $5 *1  + $1 *3 (4 個硬幣)
所以總共使用 1 + 4 = 5 個硬幣

解法:
以陣列[n1][n5][n10] 表示
在硬幣數分別為n1, n5, n10 時
可以用來買飲料的最少硬幣數

分析任何可以買飲料的硬幣組合(括號表示使用硬幣數):
1. $10 (1) /找 $1 * 2
2. $10 + $1 * 3 (4) /找 $5 * 1
3. $5 * 2 (2) /找 $1 * 2
4. $5 * 1 + $1 * 3 (4)
5. $1 * 8 (8)

飲料一次只買一瓶
寫一個 dp，每次執行代表買一瓶
上述情況都比過一輪判斷最小情況

每次買完會找錢，陣列要開得比測資範圍大
另外注意每組測資前陣列值要初始化

程式(Java):