Scribd
Upload
11 views16 pages

Dynamic Programming Fundamentals

The document provides an overview of dynamic programming, including its history, definitions, and key concepts such as subproblem division and recurrence relations. It also presents examples of dynamic programming applications, including bin packing, max independent set on a tree, and max disjoint segments. The content emphasizes the importance of solving overlapping subproblems efficiently through top-down and bottom-up approaches.

Uploaded by

Duy Phạm Hải
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
11 views16 pages

Dynamic Programming Fundamentals

The document provides an overview of dynamic programming, including its history, definitions, and key concepts such as subproblem division and recurrence relations. It also presents examples of dynamic programming applications, including bin packing, max independent set on a tree, and max disjoint segments. The content emphasizes the importance of solving overlapping subproblems efficiently through top-down and bottom-up approaches.

Uploaded by

Duy Phạm Hải
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

APPLIED ALGORITHMS

Fundamental of
optimization
DYNAMIC PROGRAMMING

3
CONTENTS

• Introduction to dynamic programming


• Examples

4
History of dynamic programming

• [Link] (1920-1984)

5
6
What is dynamic programming ?

1 2 3 4 5 6 7 8

• How many ways to travel from point 1 to point 8?

7
What is dynamic programming ?

• What is the shortest-length path to travel from point 1 to point 8?


9
2
3 4
6 3
4

1 3 2 1 3 4 4 3 5 4 6 1 7 2 8

1 3
4

4
9

8
9
What is dynamic programming ?

• Dynamic programming
• Divide the original problem into overlapping subproblems
• Recurrence relations
• Solution to a subproblem is specified based on solutions to smaller
subproblems
• Top-down approach (by recursion):
• Solve subproblems are solved recursively
• Base-case: solutions to the smallest subproblems are computed trivially (no
recursion)
• Bottom-up:
• Smallest subproblems are solved trivially
• Specify the solution to each subproblem based on the solutions to smaller
subproblems (using recurrence relations)
• Do not find the solution to the same problem more than one time
(memorization)
10
Bin packing

• Given items 1, 2, . . ., n. Item i has weight w(i) and value v(i) (i = 1, 2, . . ., n). Given a
value B, select a subset of {1, 2, . . ., n} such that the total weight is less than or
equal to B and the total value is maximal.

11
Bin packing

• Given items 1, 2, . . ., n. Item i has weight w(i) and value v(i) (i = 1, 2, . . ., n). Given a
value B, select a subset of {1, 2, . . ., n} such that the total weight is less than or
equal to B and the total value is maximal.
• Subproblem definition
• S(i, b) is the max-value of items selected from {1, . . ., i} such that the total weight
is at most b
•  b = 0, 1, 2, . . ., B:
• S(1, b) = 0 if w(1) > b, and S(1, b) = v(1), otherwise
• Recurrence relation
• S(i, b) = max{S(i-1, b), S(i-1, b-w(i)) + v(i)}, if b ≥ w(i)
S(i-1, b), otherwise

12
Max Independent Set on a Tree

• There are n objects 1, 2, . . ., n organized in a hierarchical structure:


• Each object i has a unique parent object p(i) and a value v(i)
• On top is the object that has no parent, called root 10
• Goal: Find a subset of objects such that
• No two objects have parent-child relation
3
• The sum of values of the objects in the subset is maximal 9 12

4 7 2 6 5 1

8 13 11

13
14
Max Disjoint Segments

• Given n segments 1, 2, . . ., n. Each segment i has coordiate a(i) and b(i) (a(i) <= b(i)).
Find a subset of the given segments such that no two segments have common points
and the sum of weights of selected segment is maximal.

15
THANK YOU
!

16

You might also like