Write a program that calculates the optimal number of coins from a set of given denominations to produce a given amount of currency. The correct answer should be the lowest number of total coins given.
The first line:
k d1 d2 ... dk
- where k in an integer that represents the number of coin denominations to follow on the same line.
- where d1 ... dk are integers representing the coin denominations in cents.
The second line:
n
- where n is the number of test cases to follow.
The following n lines:
a
- where a is an integer that represents the total amount of change to make in cents.
For each test case, output one line:
d1 d2 d3 ...
- where d1 ... represents one coin of any of the given denominations provided by the input.
Input:
4 1 5 10 25 # four coins: 1, 5, 10 and 25 cents
3 # three test cases
123 # 1.23 dollars
7 # 0.07 dollars
39 # 0.39 dollars
Output:
25 25 25 25 10 10 1 1 1
5 1 1
25 10 1 1 1 1
- Yes, this is a well known weakly NP-hard problem.
- This means there are a few pseudo-polynomial time solutions to this problem
- See if you can figure one of them out before you research the problem and its analogs.
sirpengi nails it: https://bitbucket.org/sirpengi/cashregister/src/tip/cash.py