Given a set of coin denomination (1,5,10) the problem is to find minimum number of coins required to get a certain amount. The greedy algorithm is to pick the largest possible denomination. I am unable to proof the correctness of this algorithm with denominations (1,5,10), How should I prove its correctness?
On the other hand if the denomination where (1,3,4,5,10) I am able to prove that for this set of denomination the greedy algorithm won't work by giving an example
For 7 greedy algorithm will pick (5,1,1)
The optimal solution is (3,4)
Is giving an example sufficient to proof that this algorithm with the set of denominations (1,3,4,5,10) doesn't work?