'Good', 'Bad' and 'Ugly' - some issues with coin systems

The change making or coin changing problem is well-known to be NP-complete (a famous class of deceptively difficult problems but technicalities therein are not the immediate concern of THIS post). The focus here is on some basic issues of change making; these are very simple to state - and to appreciate :)

Given a coinage and a target amount. Give the amount using the given set of coins with the least number of coins used. If the denominations in the coinage are say {1,2,5,10,20,50,100}, a 'greedy procedure' will do FOR ANY TARGET. This is a simple and quick-working protocol: one just keeps picking up from the coins the largest coin possible at each stage and that will give the best answer at the end (ie uses the least number of coins to change the target amount). eg: if target were 87 in the above coinage, we just add coins 50, 20, 10, 5, 2. We cannot do better than that.

However for some coinages (we could call them 'bad' ones), greedy fails to give the best breakup. If in the above example we had the denomination of 40 in addition to what is given above, 87 is best broken into 40, 40, 5,2. The greedy procedure will start with a 50 and fails to find this best solution.

What follows is my understanding of the problem (thanks to Ramana Rao for sharing his insights):

1. Just like finding the best breakup of a target for a given coinage, determining whether a given coinage is good or bad appears to be an NP complete problem in itself,

2. There could probably be a further classification within bad coinages - there are some bad coinages which can be corrected by adding a few more denominations (with the additional coins, greedy algorithms starts giving tbe best breakup) and some which are 'worse than simply bad', meaning no number of additional denominations will turn it into a good coinage. Note that coins to be added to a coinage are all larger denominations than those already there.

eg: {1,2,4,5} is a bad coinage - it fails for target amount 8 - which can be made good by adding the denomination 8.

{1,2,3,5,6} is again a bad coinage - it fails for 10 - which can be 'goodified' by adding 9.

{1 2 4 5 6 8 10} fails for 13 and cannot be made good by adding any number of coins. Any coinage got by adding new coins to this will fail for some targets. So, the badness in it is actually more and we may call this an 'ugly' coinage.

The simpler coinage of {1,3,4} is again an ugly one.

Qn: Given a coinage that is known to be bad, how does one decide whether it is ugly?

3. Most standard sources talk about only two methods to solve change making - the greedy algorithm and a dynamic programming pseudopolynomial time method (given nicely in for instance Brassard and Bratley's textbook), which always gives an optimal breakup.

Qn: Are there other in-between methods which may not be as simple and fast as 'Greedy' but can give better results (need not be optimal; could be an approximation)? Naive Greedy can at times be way off the mark.

eg: With {1,100, 150} as coinage and 200 as target, 'greedy' gives a very poor answer 150 + 1+1 +1+.... whereas the optimal 100+100 is hugely better. An in-between approach might come in handy in such cases.

4. We have assumed above that the stocks of coins of each denomination is infinite. The problem gets more real-life and difficult when the stocks of the coins available are limited. The dynamic programming method mentioned above can be made to work with minor changes if only one denomination is in limited supply but that is not really getting far. Item 3 above of finding alternative algorithms to Greedy becomes really 'urgent' here.