Consider a variant of the activity-selection problem which asks for maximizing the product of the length of selected activities instead of the number of selected activities. For example, for the activities in the example below, an optimal solution selects activities as and a with value 3 x 2 = 6. a1 9₂ = 2 a) Devise a DP program to solve this variant of the activity selection problem. It suffices to complete the first two steps of the DP algorithm. That is, define subproblems, describe the optimal value for a larger subproblem as a function of the optimal value for smaller subproblems, and write down a recursive formula for the optimal value of a subproblem (remember to include the base case). As before, assume activities are sorted by their finish time. You may use pred(i) to denote the index of the last interval that finishes before a, starts (e.g., pred(as) = as in the above example). Assume indices start at 1, and let pred(i) = 0 if no activity ends before ai. b) Emma suggests the following greedy algorithm for the problem: repeatedly select the longest interval that does not overlap previously-selected intervals. Prove or disprove whether Emma's algorithm is optimal. You must either prove that the problem admits greedy-choice property or present a counter-example in which Emma's algorithm is not optimal.
Consider a variant of the activity-selection problem which asks for maximizing the product of the length of selected activities instead of the number of selected activities. For example, for the activities in the example below, an optimal solution selects activities as and a with value 3 x 2 = 6. a1 9₂ = 2 a) Devise a DP program to solve this variant of the activity selection problem. It suffices to complete the first two steps of the DP algorithm. That is, define subproblems, describe the optimal value for a larger subproblem as a function of the optimal value for smaller subproblems, and write down a recursive formula for the optimal value of a subproblem (remember to include the base case). As before, assume activities are sorted by their finish time. You may use pred(i) to denote the index of the last interval that finishes before a, starts (e.g., pred(as) = as in the above example). Assume indices start at 1, and let pred(i) = 0 if no activity ends before ai. b) Emma suggests the following greedy algorithm for the problem: repeatedly select the longest interval that does not overlap previously-selected intervals. Prove or disprove whether Emma's algorithm is optimal. You must either prove that the problem admits greedy-choice property or present a counter-example in which Emma's algorithm is not optimal.
Operations Research : Applications and Algorithms
4th Edition
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Wayne L. Winston
Chapter19: Probabilistic Dynamic Programming
Section19.4: Further Examples Of Probabilistic Dynamic Programming Formulations
Problem 10P
Related questions
Question
Transcribed Image Text:Consider a variant of the activity-selection problem which asks for maximizing the product
of the length of selected activities instead of the number of selected activities. For example,
for the activities in the example below, an optimal solution selects activities az and as with
value 3 x 2 = 6.
a1
1
4₂ = 2
43 = 3
a4 = 1
as = 1
46 = 2
a) Devise a DP program to solve this variant of the activity selection problem. It suffices
to complete the first two steps of the DP algorithm. That is, define subproblems,
describe the optimal value for a larger subproblem as a function of the optimal value
for smaller subproblems, and write down a recursive formula for the optimal value of
a subproblem (remember to include the base case). As before, assume activities are
sorted by their finish time. You may use pred(i) to denote the index of the last interval
that finishes before a; starts (e.g., pred(as) = as in the above example). Assume indices
start at 1, and let pred(i) = 0 if no activity ends before ai.
b) Emma suggests the following greedy algorithm for the problem: repeatedly select the
longest interval that does not overlap previously-selected intervals. Prove or disprove
whether Emma's algorithm is optimal. You must either prove that the problem admits
greedy-choice property or present a counter-example in which Emma's algorithm is not
optimal.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 4 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
Recommended textbooks for you
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole