How to find out if the greedy algorithm is enough to find the minimum coin change?

Question

the minimal problem with changing coins is an NP-complete problem, but for some coin sets there is a greedy algorithm (first choose the names of the items). Given a set of integers representing the values ​​of the coins, what is the fastest algorithm that determines if the greedy algorithm is sufficient or not? One obvious way is to create your solution for dynamic programming to the highest denomination and see each one if it gives a better solution than the greedy way. But is there a faster “mathematical path” to detect it?

Answer 1

A greedy algorithm will work if the following selection creates a target amount: (there may be more complex formats that will work, but it's simple and linear to check)

Let 1 appear selected. The set of the largest item will look like this:

 11...1100...00100...00 

That is, zero or more are selected from the largest and one other item is selected.

Why this is optimal is easy to prove. Let C = s elements selected from the largest, then we know that C creates the maximum possible sum for any s or smaller elements, since if you replaced any element with C, you would need to do this with a lower level, since the largest s elements are already selected (and deleting will also clearly reduce the cost). Since C produces a value less than the target (because of this one more element is required), we need at least one more element to get to the goal, so the minimum number of elements needed to achieve the goal is s + 1, which completes evidence.

This requires O (n), 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, as well as the trivial case where target = 0, which needs to be checked if allowed.

The above requires a target amount, if you want to check many target amounts, you can probably generate all the possible amounts using the above method in O (n ^ 2) and have a card of the amount in the account and just do a search to get the value if it exists.

EDIT: Branch and bound

As an extension of the foregoing and an alternative to DP, I offer brute force handled with greed by branch and binding. Using the same argument as above, you know that you can skip the current path if bestCoins has the value and (currentSum + (bestCoins - currentCoins) * currentItem.value) < target .

Please note that this may fail in some problems and work fine on others (I think it depends a lot on how early we find a decent solution). To avoid forever, you can store the minimum possible number of coins in the optimal solution (obtained from viewing the first elements until we reach the goal similar to the one above) and cut the paths away from this.

If you do it right, you can run it for a short time, and if it completes, and we have a solution, we have an optimal solution, if not, we won’t lose too much time and can run another algorithm, such as DP.

Answer 2

I recently came up with 1 solution, which seemed to show that the given 2 conditions were satisfied, the greedy algorithm would give the optimal solution.

a) GCD (All items except 1) = 2nd lowest nominal.

b) The sum of any two consecutive denominations must be less than the third denomination.

For example, c2 + c3 <c4.

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

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

Answer 3

A greedy solution only works for certain items in relation to a certain amount in order to make changes.

The step of adding back when it is added, then it is no longer greedy, and ultimately it finds all possible solutions, and therefore, this is not a dynamic programming problem.

Example: consider coinage = [2, 5], and the amount to be changed is 16. The greedy first solution naturally searches for the highest names first [5, 5, 5], and then it gets stuck at 1. The countdown step gives another solution [5, 5, 2, 2, 2].