The minimum coin change problem is an NP-complete problem but for certain sets of coins the greedy algorithm (choose largest denominations first) works. Given a set of integers denoting coin-values, what's the fastest algorithm to determine if the greedy algorithm suffices or not? One obvious way is to build up your dynamic programming solution till the largest denomination and see for each if it yields a better solution than the greedy way. But is there a faster "math-way" of detecting it?
The greedy algorithm would work if the following selection produces the target amount: (there may be more complex formats which would work, but this is simple and linear to check)
Let 1 represent selected. The set, from the largest denomination, would look like:
11...1100...00100...00
That is, zero or more selected from the largest, and a single other element selected.
Why this is optimal is simple to prove. Let C = the s elements selected from the largest, then we know that C produce the largest possible sum for any s or less elements, since, if you were to replace any element in C, you would have to do so with a lower-valued element, since the s biggest elements are already selected (and removing would also obviously decrease the cost). Since C produces a value less than the target (because of that one other element required), we need at least one other element to get to the target, thus the minimal amount of elements required to get to the target is s+1, which concludes the proof.
You need O(n) to evaluate this, and this can be done as follows: (in Java)
int[] sortedCoins = ...;
int sum = 0, selectionCount = 0, i = 0;
for (; i < sortedCoins.length; i++)
{
sum += sortedCoins[i];
if (sum >= target) break;
selectionCount++;
}
sum -= sortedCoins[i]; // we added the element to push us over, so remove it again
for (; i < sortedCoins.length; i++)
{
if (sum + sortedCoins[i] == target)
return selectionCount+1;
}
return -1; // not found
Oh, and there's also a trivial case where target = 0 which needs to be check if it's allowed.
The above requires a target amount, if you want to check many target amounts, you can probably generate all possible sums with the above method in O(n^2) and have a map of the sum to the count and just do a lookup to get the value if it exists.
EDIT: Branch and bound
As an extension to the above and an alternative to DP, I suggest brute force processed greedily with branch and bound. Using a similar argument as above, you know you can skip the current path if bestCoins has a value and (currentSum + (bestCoins - currentCoins) * currentItem.value) < target.
Note that this can fail miserably on some problems and work wonderfully on others (I think it depends largely on how early we find a decent solution). To avoid taking forever, you can store the minimum possible number of coins in the optimal solution (derived from looking at the first elements until we reach the target, similar to above), and cut off paths far from this.
If done right, you should be able to run it for a short time, and if it ran to completion and we have a solution, we have the optimal solution, if not, we didn't lose too much time and can run another algorithm like DP.