I've not followed this thread in detail so I don't know if it's already been mentioned, but this is indeed a well known mathematical (combinatorial) problem, and a "hard" one, actually called "the money changing problem".
in reply to Golf: Buying with exact change
The problem is discussed in some detail e.g. in the beautiful book generatingfunctionology by Prof. Wilf, available for download from http://www.math.upenn.edu/%7Ewilf/DownldGF.html
To quote from Wilf:
There are no general `formulas' for the conductor if M >= 3, and no good algorithms for calculating it if M >= 4.
(M is the number of "changes" and the "conductor" is the smallest quantity N such that all n>=N can be represented as sums of the changes. In this case the latter must be -of course- coprime.)