Standard 16: Dynamic Programming 1: Algorithms

Short description: Execute a given DP algorithm on examples; identify DP components and failures.

Relevant notes: Topic F: Dynamic Programming.

Full description

Given a DP problem and algorithm, identify each of the DP components of the algorithm. Execute the algorithm on a given example, filling in the array and giving the final answer. Identify failures of incorrect variants.

Example problem

Consider the problem of knapsack with duplicates allowed:

Here is a dynamic programming algorithm: 


1 knapsack_dups(v, w, W):
2     let C[0] = 0
3     for x = 1 to W:
4         C[x] = C[x-1]
5         for i = 1 to n, if w[i] <= x:
6             C[x] = max(C[x], v[i] + C[x - w[i]])
7     return C[W]

Part a. What are the DP components of this solution? Briefly explain each.

Part b. Execute the algorithm on the following input, including filling in the array C. Let $W = 9$. For x = 0 to 4, briefly describe how you arrived at the value you found for C[x].

ItemValueWeight
142
253
385

Sample solution

Sample solution.

Part a.

Subproblem definition: C[x] = the maximum possible value for a set of items with duplicates of total weight at most x, for x = 0 to W.

Recurrence, base case: C[0] = 0, meaning that a weight limit of zero has a value of zero.

Recurrence, inductive case: C[x] = max(C[x-1], max_i v[i] + C[x - w[i]]), where the inner maximum is only over items i where w[i] <= x. Explanation: the maximum value for weight x is either the maximum value for weight x-1, where we just use that same set of items; or the maximum, over all items that can fit, of the best value of including a copy of that item and then optimally using the remaining space.

Final answer: we just return C[W], because that equals the original problem.

Reconstructing the object: not part of this solution.


Part b.

x0123456789
C[x]00458912131617

C[0] was the base case. For C[1], none of the items fit, so the only choice in the recurrence was C[1-1] = C[0] = 0. For C[2], only item 1 fit, with weight 2 and value 4, so C[2] = 4. For C[3], we could either fit item 1 or 2. Item 1 gave value 4 + C[1] = 4. Item 2 gave value 5 + C[0] = 5. So item 2 was better. For C[4], we could either fit item 1 or 2. Item 1 gave value 4 + C[2] = 8. Item 2 have value 5 + C[1] = 5. So item 1 was better.

The final answer is C[9] = 17.

Rubric

Rubric.

To pass, a solution must follow the course requirements for writing and proofs.

To pass, a solution must pass both parts. For Part a, each component must be clearly identified, except that Reconstructing can be omitted in this case. Each component must have a correct, brief explanation. However, these explanations can be brief and not comprehensive, as long as the component was identified correctly.

For Part b, the table and final answer must be filled in correctly. A solution may still pass if it forgets to include x=0, if everything else is filled in correctly. The explanations for x=0,...,4 must be correct, but can be brief and not comprehensive.

The numerical rubric for this problem is:

  • 4 (Pass, Near-Perfect): correct answers, clear, brief.
  • 3 (Pass, Proficient): correct answers. In Part a, may omit Reconstruction and may be a bit brief or unclear if components are still correctly identified. In Part b, may omit the x=0 case if everything else is correct, and may have imperfect explanations for x=0,...,4 as long as nothing is incorrect or overly lengthy.
  • 2 (Fail, Progress): one or more incorrect answers. In Part a, may not correctly identify or name one of the components, or may give a clearly incorrect explanation. In Part b, may have a mistake in the table or may mistakenly mis-apply the recurrence in the explanations for x=0,...,4.
  • 1 (Fail, Wrong Track): Missing or mis-identifying most components of DP solution in Part a; appears to be on the wrong track for filling in the table in Part b.