Return to Revisions

Since you asked for mathematical background...

In general, the Change-making problem is a knapsack problem, which is NP-hard. However, for sane sets of currency denominations, a simple greedy algorithm works.

For your set of denominations, { 1000, 500, 300, 100, 50 }, the greedy algorithm applies. (There is, however, an amount with two optimal solutions: 600 =わ 500 +たす 100 =わ 300 +たす 300.) Therefore, your greedy algorithm and @MartVandeVen's simplified implementation of it will work.