Differences

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

Link to this comparison view

cs-312:hw16.5 [2014/12/31 23: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.
  
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