Weighted Activity Selection using Dynamic Programming

This is a C++ Program that Solves Weighted Activity Selection problem using Dynamic Programming technique.

Problem Description

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.

Problem Solution

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.

Expected Input and Output

Case-1:

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

Program/Source Code

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.

```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
struct activity
```
```
{
```
```
    int s,e,v;
```
```
};
```
```
 
```

int weightedActivity(int n, vector<activity> &a)

```
{
```
```
    if(n==1)
```
```
        return a[0].v;
```
```
 
```
```
    vector<int> dp(n);
```
```
    dp[0]=a[0].v;
```
```
    int x,y,i,j;
```
```
 
```
```
    for(i=1;i<n;i++)
```
```
    {
```
```
        x=a[i].v;
```
```
 
```
```
        j=i-1;
```
```
        while(j>=0 && a[i].s<=a[j].e)
```
```
        {
```
```
            j--;
```
```
        }
```
```
 
```
```
        y=0;
```
```
        if(j!=-1)
```
```
            y=a[j].v;
```
```
 
```
```
        dp[i]=max(x+y,dp[i-1]);
```
```
    }
```
```
 
```
```
    return dp[n-1];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,n;
```

    cout<<"Enter the number of activities ";

```
    cin>>n;
```
```
 
```

    cout<<"Enter the start time, end time and value of each activity "<<endl;

```
 
```
```
    vector<activity> a(n);
```
```
 
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>a[i].s>>a[i].e>>a[i].v;
```
```
    }
```
```
 
```

    cout<<"The maximum attainable value of activities is"<<endl;

```
    cout<<weightedActivity(n,a);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

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.

Runtime Test Cases

 
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.

Note: Join free Sanfoundry classes at Telegram or Youtube

« Prev - Treats for the Cows – Dynamic Programming Solutions

» Next - Assembly Line Scheduling using Dynamic Programming

Related Posts:

Practice Computer Science MCQs
Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books
Apply for Computer Science Internship

Recommended Articles: