Homework Assignment #16

To solve an instance of the optimal coin change problem using dynamic programming where a greedy algorithm would fail.

Show all work neatly.

Now consider a coin system for which we know the greedy algorithm would fail to always provide optimal change: $d=[1,5,8]$. Show how to use dynamic programming to optimally make change for 10 units.

Yes or No: Did you read all of Section 6.3 in the textbook?