1. Find the solution set of the following Activity-selection Problem. ai 1 Si 3 fi...

Transcribed Image Text:

1. Find the solution set of the following Activity-selection Problem. ● ai 1 Si 3 fi 5 By earliest starting time: sorting starting time (s;) in non-decreasing order. By earliest finish time: sorting finishing time (f;) in non-decreasing order. By shortest interval: sorting (fi – s;) time in non-decreasing order. 2 3 1 0 4 6 4 12 14 5 5 9 6 8 11 7 3 8 8 2 13 9 8 12 10 6 10 11 5 7 2. Find the maximum profit on an input with items of weights 3 lb., 2 lb., 1 lb., 4 lb., 5 lb. and values $25, $20, $15, $40, and $50, respectively using fractional Knapsack approach using ratio greedy strategies. The knapsack capacity is 6 lb. 1. Find the solution set of the following Activity-selection Problem. ● ai 1 Si 3 fi 5 By earliest starting time: sorting starting time (s;) in non-decreasing order. By earliest finish time: sorting finishing time (f;) in non-decreasing order. By shortest interval: sorting (fi – s;) time in non-decreasing order. 2 3 1 0 4 6 4 12 14 5 5 9 6 8 11 7 3 8 8 2 13 9 8 12 10 6 10 11 5 7 2. Find the maximum profit on an input with items of weights 3 lb., 2 lb., 1 lb., 4 lb., 5 lb. and values $25, $20, $15, $40, and $50, respectively using fractional Knapsack approach using ratio greedy strategies. The knapsack capacity is 6 lb.

Answer rating: 100% (QA)

1 By earliest starting time sorting starting time si in nondecreasing order Explanation For the activityselection problem using the earliest starting time approach we sort the activities in nondecreas... View the full answer