##### Differences

This shows you the differences between two versions of the page.

 — cs-312:hw16.5 [2014/12/31 16:04] (current)ringger created 2014/12/31 16:04 ringger created 2014/12/31 16:04 ringger created Line 1: Line 1: + = Homework Assignment #16.5 = + + == Objective == + To solve an instance of the 0/1 knapsack problem, and to gain more experience applying dynamic programming to a new problem: the maximum contiguous subsequence sum problem. + + == Exercises == + Show all work neatly. + + ===Question 1=== + + 0/1 Knapsack: Use dynamic programming to fill a knapsack having a weight capacity of 12 units with a load of maximum value from the following set of objects: + * Weights: 1, 2, 5, 6, and 7 units + * Values: 1, 7, 11, 21, and 31, respectively. + Your answer should include: + * a table with solutions to sub-problems + * the value of the optimal load + * the objects to be included in the optimal load (keep back-pointers in the table if you want) + + ===Question 2=== + + Problem 6.1 in the text.  To solve this problem, you are designing a new algorithm by appling our 6-step process of Dynamic Programming. ​ Show each step.  For step 5, describe how you will store the sub-problem solutions (specify the dimensionality of the table) and then use the example problem in the book's exercise. ​ For step 6, describe how to analyze/​back-trace in your table of sub-problem solutions to extract the composition of the answer. Then use the example problem in the book's exercise. ​ It should be clear how the steps are accomplished. [3 points for each step] + + '''​For your reference here are the 6 steps:'''​ + # Ask: Am I solving an optimization problem? + # Devise a minimal description (address) for any problem instance and sub-problem. + # Divide problems into sub-problems:​ define the recurrence to specify the relationship of problems to sub-problems. + # Check that the optimality property holds: An optimal solution to a problem is built from optimal solutions to sub-problems. + # Store results – typically in a table – and re-use the solutions to sub-problems in the table as you build up to the overall solution. + # Back-trace / analyze the table to extract the composition of the final solution. 