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:
- where n is the number of test cases to follow.
The following n lines:
- 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.
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
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.