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:

  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.
cs-312/hw16.5.txt · Last modified: 2014/12/31 23:04 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0