Instantly share code, notes, and snippets.

# sixthgear/gist:3343998 Created Aug 13, 2012

Cash Register Problem

# Cash Register Problem

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.

## Input

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.

## Output

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.

## Example

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
``````

## Test Cases

http://progg.it/dl/change.zip

### Notes

• 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 commented Aug 15, 2012

 sirpengi nails it: https://bitbucket.org/sirpengi/cashregister/src/tip/cash.py