Description
Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed or not compliant with the specification. Submit your homework via Blackboard as one PDF or Word document. Refer to the grading guidelines posted on Blackboard to understand how the submitted exercises will be graded.
-
(25) [Knapsack: finding the optimal subset] Consider the integer knapsack problem. Give a recursive – not iterative — algorithm (call it Find-Optimal-Subset) that finds the optimal subset of items through post-processing, that is, after filling in the memorization table to find the maximum total value of the optimal subset of items. (The algorithm we studied in class finds only the maximum total value, not the actual optimal subset of items.) Hint: Trace back through the array M[0..n,0..W] following the optimal substructure.
-
(25) [Algorithm design: shipping carrier scheduling] Textbook Exercise 11 in Chapter 6. Show the optimal substructure (with an explanation), give the memoized bottom-up dynamic programming algorithm, and state the resulting running-time complexity (with an explanation).
