I have reasons to believe that there is a faster way to confirm, that for coin denomination systems if the greedy solution yields the optimal solution or not.

I believe that if you check that for all values from the Largest denomination to 2nd largest denomination, the greedy solution is the optimal solution, then for that custom coin denomination system, the greedy solution will always yield the optimal solution.

For example.

1,5,7 <- For this greedy solution != optimal always as for values n = [7,5+7] ; n = [7,12], for n = 10, optimal (5,5) != greedy (7,1,1,1)

1,7,13,19,61 <- Greedy Solution == optimal always as for values n = [61, 61 + 19] ; n = [61, 81] greedy is always optimal

1,7,14,20,61 <- greedy solution != optimal always as for values n = [61, 61+20] ; n = [61, 81] for n = 80, optimal (20,20,20,20) != greedy (61,14,1,1,1,1,1,1)

I was wondering if this has already been discovered or not? If so, is there a proof that I can be pointed to? If not, can I know how should I go about proving this point?

  • 1
    $\begingroup$ Take coin values 1, 800, 999 and 1,000. Greedy is optimal for 999..1,000, that is the second largest to the largest. Greedy is not optimal for 1,600 which will take 601 coins instead of 2. Your examples don't match your description. $\endgroup$ – gnasher729 Nov 17 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.