관심있는것들

want to maxmize weight by scheduling Greedy no longer works Dynamic Programming define the subproblem == Rx R == nubmer of request , x == f(i) finishing time , Rf(i) ~= request later than f(i) Rx = {j ∈ R|s(j) ≥ x} given particular x i can always shrink nubmer of request that i have based on {s(j} >=x} (rule) Dp guessing Try each request i as a possible First Solution // n subproblems * subprobl..

Convex Hull S = {(xi, yi)|i = 1, 2,...,n} assume no two have same x coordinate, no two have same y coordinate, and no three in a line for convenience Convex Hull ( CH(S) ) == smallest convex polygon containing all points in S Brute force Test each line segment to see if it makes up an edge of the convex hull • If the rest of the points are on one side of the segment, the segment is on the convex..

With given intervals, want to maxmize possible nubmer of intervals by scheduling Greedy algorthim 1. Use a simple rule to select a request i 2. Reject all requests imcompatible with i 3. Repeat until all request are processed // basic template but no rules we need to specifiy the rules Possible rules 1. Select request that start earliest 2. Select request that has smallest interval 3. For each r..