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.

Question 1

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.

Question 2

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

cs-312/hw16.txt · Last modified: 2015/02/18 22:34 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0