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

— |
cs-312:hw16.5 [2014/12/31 16:04] (current) 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. | ||