数年前に某へなちょこで出した問題。
あなたは硬貨を何枚か持っており、ある金額を払いたい。
お釣りの金額が最小となるような硬貨の組み合わせと、その場合のおつりを計算せよ。
硬貨の価値はすべて正の整数、払いたい金額も正の整数で、オーバーフローは考慮しなくても良いとする。
お金が足りない場合も考慮しなくてよい。
最良の組み合わせが複数ある場合、そのうちひとつを出力すればよい。
＃ちなみに。C++で書いて、40分 / 50行 ほどでした。
実行例：
# 払いたいのは100円で、20円玉・30円玉・40円玉・50円玉・60円玉・70円玉 を持っている。
>coins 100 20 30 40 50 60 70
金額 : 100, 支払い : [20, 30, 50], おつり : 0
# 払いたいのは100円で、20円玉4枚・29円玉2枚 を持っている。
>coins 100 20 20 20 20 29 29
金額 : 100, 支払い : [20, 20, 20, 20, 29], おつり : 9
# 払いたいのは100円で、31円玉・37円玉・41円玉・43円玉・47円玉 を持っている。
>coins 100 31 37 41 43 47
金額 : 100, 支払い : [31, 37, 41], おつり : 9
>coins 200 38 43 47 49 56 59 64 66 76 95
金額 : 200, 支払い : [38, 47, 49, 66], おつり : 0
>coins 3000 468 575 603 635 647 679 778 790 825
金額 : 3000, 支払い : [468, 575, 635, 647, 679], おつり : 4
>coins 500 31 39 54 55 60 60 61 63 66 70 74 75 88
金額 : 500, 支払い : [31, 39, 54, 55, 60, 60, 61, 66, 74], おつり : 0
>coins 1000 32 33 34 35 38 40 46 47 48 49 50 50 51 51 52 53 59 61 61 62 62 63 65 71 73 75 78 78 80 81 85 90 92 95 98
金額 : 1000, 支払い : [32, 33, 34, 35, 38, 40, 46, 47, 48, 49, 50, 50, 51, 51, 52, 53, 59, 61, 73, 98], おつり : 0
>coins 10000 366 390 440 442 490 504 509 520 521 557 624 651 684 708 730 734 763 783 790
金額 : 10000, 支払い : [366, 390, 440, 442, 490, 504, 509, 520, 557, 624, 651, 708, 730, 734, 763, 783, 790], おつり : 1
