演算法›Ch3 動態規劃
第 25 題/共 40 題
◀ AL 25/40
25. Weighted Interval Scheduling、Dynamic Programming
#AL-03-025易Weighted Interval SchedulingDynamic Programming

We offer nn courses where each course ii has a start time sis_i, a finish time fif_i, and a weight wiw_i. Two courses are considered compatible if their time intervals do not overlap. For simplicity, we can assume that the courses are sorted in non-decreasing order of their finish times, denoted as f1≤f2≤⋯≤fnf_1 \le f_2 \le \cdots \le f_n. Additionally, let p(j)p(j) for a course jj represent the largest index i<ji < j such that courses ii and jj are disjoint. We define p(j)=0p(j) = 0 if no course i<ji < j is disjoint from jj. Our goal is to find a set S⊆{1,…,n}S \subseteq \{1, \ldots, n\} of mutually compatible courses such that the total weight of the courses in SS is maximized. We have designed a recursive algorithm for this purpose, but we have omitted an essential part. Please assist us in completing the missing portion. Hint: This algorithm returns the value of the optimal solution to the problem consisting of courses {1,…,i}\{1, \ldots, i\}.

F(i)
    If i = 0 return 0
    return ______
📄 成大114
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch3 動態規劃
本章題號 · 21–40 / 40