How to tell if greedy algorithm suffices for findi

Question

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?

Answer 1

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.

Answer 2

The greedy solution works only for certain denominations, with respect to the certain amount to make the change for.

A backtracking step when added, then it's not a greedy anymore, and this considers, eventually, a find all possible solutions, and hence it's neither a dynamic programming problem.

Example: consider the coinage = [2, 5], and the amount to be changed is 16. A greedy first solution is naturally looking for the greatest denominations first, [5, 5, 5] and then it stuck at 1. A backtracking step yields another solution [5, 5, 2, 2, 2].

Answer 3

I recently came up with 1 solution that seemed to show if the given 2 conditions are satisfied, the greedy algorithm would yield the optimal solution.

a) The G.C.D (All the denominations except 1) = 2nd Smallest denomination.

b) The sum of any 2 consecutive denominations must be lesser than the 3rd consecutive denomination.

For eg. c2 + c3 < c4.

(Where c1 = 1; c2, c3, c4 are coin denominations in ascending order).

I understand this is not a complete solution. However, I believe that if these 2 conditions are met, the greedy algorithm will yield the optimal solution.