文档介绍：Algorithm Design and Analysis
LECTURE 19
Dynamic Programming
•Knapsack problem
•RNA Secondary Structure
Adam Smith
10/8/2008
A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne
Review questions
• Shortest-path(G,s,t) = shortest route from s to t.
• Longest-path(G,s,t) = longest simple path
from s to t
• Question: Do Shortest Path and Longest Path
have optimal substructure that can be used for a
poly-time dynamic programming algorithm?
– What if the graph is a DAG?
10/8/2008
A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne
Knapsack Problem
• Given n objects and a "knapsack."
-Item i weighs wi > 0 kilograms and has value vi > 0.
-Knapsack has capacity of W kilograms.
-Goal: fill knapsack so as to maximize total value.
• Ex: { 3, 4 } has value 40.
W = 11
• Many “packing” problems fit this model # value weight
– Assigning production jobs to factories 1 1 1
– Deciding which jobs to do on a single 2 6 2
processor with bounded time 3 18 5
– Deciding which problems to do on an exam 4 22 6
5 28 7
10/8/2008
A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne
Knapsack Problem
• Given n objects and a "knapsack."
-Item i weighs wi > 0 kilograms and has value vi > 0.
-Knapsack has capacity of W kilograms.
-Goal: fill knapsack so as to maximize total value.
• Ex: { 3, 4 } has value 40.