Homework Assignment #16.5

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.

Show all work neatly.

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)

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:

1. Ask: Am I solving an optimization problem?
2. Devise a minimal description (address) for any problem instance and sub-problem.
3. Divide problems into sub-problems: define the recurrence to specify the relationship of problems to sub-problems.
4. Check that the optimality property holds: An optimal solution to a problem is built from optimal solutions to sub-problems.
5. 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.
6. Back-trace / analyze the table to extract the composition of the final solution.