This is a C++ Program that Solves Weighted Activity Selection problem using Dynamic Programming technique.
There are N jobs. Each job has a start time, end time and value. You have to attain the maximum value by performing these jobs. However, you can do only one job at a time.
We create a structure for activity information. Also, we will create an array to memoize values computed. For every activity, we will find out the maximum value attainable at this point.
N=4 Job start time end time value 1 1 2 100 2 4 5 70 3 6 30 150 4 3 100 200 Maximum attainable value = 300
Here is source code of the C++ Program to Solve Weighted Activity Selection problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
using namespace std;
int weightedActivity(int n, vector<activity> &a)
while(j>=0 && a[i].s<=a[j].e)
cout<<"Enter the number of activities ";
cout<<"Enter the start time, end time and value of each activity "<<endl;
cout<<"The maximum attainable value of activities is"<<endl;
In the main function, we take inputs for the start time, end time and value of each activity. We pass these values to function weightedActivity as parameters. This function will return the result to be displayed on the standard output.
Case-1: $ g++ weighted_activity.cpp $ ./a.outEnter the number of activities 4 Enter the start time, end time and value of each activity 1 2 100 4 5 70 6 30 150 3 100 200 The maximum attainable value of activities is 300
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.