Skip to content

Instantly share code, notes, and snippets.

@sixthgear
Created August 13, 2012 20:50
Show Gist options
  • Save sixthgear/3343998 to your computer and use it in GitHub Desktop.
Save sixthgear/3343998 to your computer and use it in GitHub Desktop.
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
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment