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.
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?