FOR FREE CONTENT
Weighted Activity selection (Dynamic Programming)
Back to ProgrammingDescription
Weighted activity scheduling problem: Given a set of activities N to be processed on a machine where each activity i ∈ N has a start time si and finish time fi and weight wi. Two activities i and j are said to be non-conflicting if si ≥ fj or sj ≥ fi. The objective is to find a set of non-conflicting activities such that the total weight is maximum.
Dynamic Programming: Dynamic Programming is a method for solving a problem by breaking it down into sub problems which are overlapping and, optimally solving each of those sub problems exactly once while storing their solutions state (optimal substructure)
Dynamic Programming approach to weighted activity scheduling problem: The set of activities are sorted in ascending order of their finishing time. A table is created to store and add the weight of non-conflicting activities (subproblems) and using the result stored in the table the maximum total weight is calculated (optimal substructure).
Procedure:
Consider the following set of activities and their start time and finish time in the table below,
Next, the activities are sorted in ascending order of their finishing time as shown below.
We create a table of size 4 (no. of activities) to store the added weights and initialize it with the weight of each activity. Consider a1 as j and a2 as i such that (j ≠ i).
We start from j and check if it is non-conflicting with i. Since s2 ≤ f1 (or 1 ≤ 5), i moves on to a3 and j again starts from a1 and no change is made to the weight table.
We see that i and j are non-conflicting since s4 ≥ f1 (or 6 ≥ 5), so we add their weights wi+wj = w4+w1 = 75 + 25 = 100. We store 100 in the ith position and j moves on to a2 as shown below.
We see that i and j are non-conflicting since s4 ≥ f2 (or 6 ≥ 2), so we add their weights wi+wj = w4+w2 = 100 + 50 = 150. We store 100 in the ith position and j moves on to a2 as shown below.
Next, i moves on to a3 and j again starts from a1 as shown below.
Continuing with the same process, we will see that for j = a1 and j = a2 and j = a4, all are conflicting with i. The process stops when i is at the last position. The final result i.e. the total weight is found at the second last position in the table. So the total weight = 150.
Algorithm
Algorithm:
Input:
1. An array of Activities consisting of Activity ID, Start Time , Finish Time & Weight.
Output:
1. Displays the maximum weight possible after scheduling non-conflicting activities.
Algo:
Step 1: Start
Step 2: Define user defined datatype Activity with Activity ID, Start Time, Finish Time & Weight.
Step 3: Defining the Input Activity function
void inputActivity (struct Activity activity[], int activitySize)
for i = 0 to i < activitySize repeat
Display “Input for Activity ” (i+1)
Display “Enter Activity ID”
Read activity[i].activityID
Display “Enter Activity Start Time”
Read activity[i].startTime
Display “Enter Activity Finish Time”
Read activity[i].finishTime
Display “Enter Activity Weight”
Read activity[i].weight
Step 4: Defining the Sort function
void sort(struct Activity activity[], int activitySize)
for i = 0 to i < activitySize repeat
Set flag -> 0
for j = 0 to j < (activitySize-i-1) repeat
Check if(activity[j+1].finishTime < activity[j].finishTime)
Set temp -> activity[j+1]
Set activity[j+1] -> activity[j]
Set activity[j] -> temp
Set flag ->1
Check if(flag == 0)
break
Step 5: Defining the Binary Search function
int binarySearch(struct Activity activity[], int currentActivity)
Set low -> 0
Set high -> (currentActivity – 1)
While(low <= high) do
Set mid -> (low + high) / 2
Check if(activity[mid].finishTime <= activity[currentActivity].startTime)
Check if (activity[mid + 1].finishTime <= activity[currentActivity].startTime)
Set low-> (mid + 1)
Otherwise
Return mid
Otherwise
Set high -> (mid - 1)
Return -1
Step 6: Defining Calculate Weight function
void calculateWeight(struct Activity activity[], int activitySize)
Set int dynamic[activitySize] ->Null
Set dynamic[0] -> activity[0].weight
for i = 0 to i < activitySize repeat
Set int currentWeight -> activity[i].weight
Set int activityIndex -> binarySearch(activity, i)
Check if(activityIndex ≠ -1)
Set currentWeight -> currentWeight + dymanic[activityIndex]
Check if(currentWeight > dynamic[i – 1]
Set dynamic[i] -> currentWeight
Otherwise
Set dynamic[i] ->dynamic[i – 1]
Set int totalWeight -> dynamic[activitySize – 1]
Display totalWeight
Step 7: Defining Main function
Display “Enter Activity Size”
Read activitySize
Set Activity activity[activitySize] -> Null
Call inputActivity(activity, activitySize)
Call sort(activity, activitySize)
Call calculateWeight(activity, activitySize)
Code
Characteristics of Weighted Activity selection problem:
● It requires the activities to be sorted in ascending order of finish time.
● The algorithm follows dynamic programming paradigm
● It requires an extra space for storing the weights of activities and hence, its space complexity is O(n) where n is the size of the array in which it is stored.
● In the Activity scheduling problem, the objective is to maximize the number of non-conflicting activities, whereas in the weighted activity scheduling problem the objective is to maximize the summation of weights of non-conflicting activities.
Application:
● Weighted activity selection problem finds its application in the field of Operation Research.
Advantage:
● Since the algorithm follows a dynamic programming paradigm, it speeds up the processing as we use previously stored calculations of the subproblems.
● If the activities are sorted in ascending order of their finishing time, the algorithm takes only O(nlogn) time.
Disadvantage:
● The activities must be sorted in ascending order of their finish time.
● If the activities are not sorted, the algorithm takes either O(n2) time or O(nlogn) time depending on the sorting algorithm.
● Since the algorithm follows a dynamic programming paradigm, the calculated values of the subproblems are stored, which consumes memory.
Complexity:
Time Complexity:
(1) If the activities are sorted in ascending order of their finish time, the modified bubble sort function sort() takes O(n) time where n is the number of activities. In the calculateWeight() function, we iterate each activity and call the binary search function for each activity which takes O(logn) time. Thus, the calculateWeight() function takes O(nlogn) time. Hence, the total time complexity if the activities are sorted is O(nlogn).
(2) If the activities are not sorted, the sort() function takes O(n2) time. The complexity of the calculateWeight() function is the same as in point (1). Hence, the total time complexity is O(n2) + O(nlogn) = O(n2). This can be further optimized by using quicksort or heap sort instead of bubble sort which takes O(nlogn) time.
Space Complexity:
It requires an extra space for storing the weights of activities and hence, its space complexity is O(n) where n is the size of the array in which it is stored.
