I have a currency where each subsequent coin is twice as valuable as the one before it.
I need to prove that for any amount of change needed, the greedy algorithm for making change (always choosing largest amount first than using the next largest and so on) will give the minimum amount of change.
Either that or I need to show that the algorithm wouldn't work by giving a counterexample.
How can I write a proof for this?