In the JOBSELECTION problem, the input is a positive integer t and a sequence of n...

 

Transcribed Image Text:

In the JOBSELECTION problem, the input is a positive integer t and a sequence of n pairs of positive integers (r1, p1), (r2, P2),..., (rn, Pn) that correspond to the reward ri you earn if you complete job i and the penalty p; that you must pay if you do not complete job i. You can only complete t jobs; a valid solution to the problem is a subset S C {1, 2, ..., n} of |S| = t jobs that maximizes the profit profit(S) = ri - Pj earned by completing the set S of jobs. iES jES Design a greedy algorithm to solve this optimization problem. Prove that it always returns an optimal solution. Justify correctness and analyze running time. Activate Windows In the JOBSELECTION problem, the input is a positive integer t and a sequence of n pairs of positive integers (r1, p1), (r2, P2),..., (rn, Pn) that correspond to the reward ri you earn if you complete job i and the penalty p; that you must pay if you do not complete job i. You can only complete t jobs; a valid solution to the problem is a subset S C {1, 2, ..., n} of |S| = t jobs that maximizes the profit profit(S) = ri - Pj earned by completing the set S of jobs. iES jES Design a greedy algorithm to solve this optimization problem. Prove that it always returns an optimal solution. Justify correctness and analyze running time. Activate Windows