New answers tagged proof-techniques
1
vote
Accepted
Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem
I decided to write a python script that generates all the optimal solutions for all the change. You can literally scroll through the solutions and observe there are no denomination expansions. So, my ...
1
vote
Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem
The greedy algorithm is optimal if it only picks 1c coins. It is optimal if it picks a 5c coin as the highest because the alternative is five 1c. It is optimal if it picks one or two 10c because the ...
- 28.4k
Top 50 recent answers are included