# 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

### 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.

Back to top