Algorithms & Data Structures (Winter 2021) Algorithm Paradigms – DP3 + Greedy
Announcements
Copyright By PowCoder代写 加微信 powcoder
• Complete Search
• Divide and Conquer.
• Dynamic Programming. • Introduction.
• Examples.
• Introduction. • Examples.
DP– Activity-selection Problem
• Input: Set S of n activities, a1, a2, …, an. • si = start time of activity i.
• fi = finish time of activity i.
• Output: Subset A of maximum number of compatible activities.
• 2 activities are compatible, if their intervals do not overlap.
Activities in each line are compatible.
0 1 2 3 4 5 6 7 8 9 10
DP– Activity-selection Problem
i1234567 si 0 1 2 4 5 6 8
2 3 5 6 9 9 10 Activities sorted by finishing time.
a2fsa5 f 255
s a1 114477
0 1 2 3 4 5 6 7 8 9 10
f s a4 f s a7 f
Optimal compatible set: { a1 , a3 , a5 }
DP– Activity-selection Problem
Step 1: Identify the sub-problems (in words). Step 1.1: Identify the possible sub-problems.
ì Let Sij = subset of activities in S that start after ai finishes and finish before aj starts.
S=a∈S:∀i,j f≤s