# 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.

1. `#include<bits/stdc++.h>`
2. `using namespace std;`
3. ` `
4. `struct activity`
5. `{`
6. `    int s,e,v;`
7. `};`
8. ` `
9. `int weightedActivity(int n, vector<activity> &a)`
10. `{`
11. `    if(n==1)`
12. `        return a[0].v;`
13. ` `
14. `    vector<int> dp(n);`
15. `    dp[0]=a[0].v;`
16. `    int x,y,i,j;`
17. ` `
18. `    for(i=1;i<n;i++)`
19. `    {`
20. `        x=a[i].v;`
21. ` `
22. `        j=i-1;`
23. `        while(j>=0 && a[i].s<=a[j].e)`
24. `        {`
25. `            j--;`
26. `        }`
27. ` `
28. `        y=0;`
29. `        if(j!=-1)`
30. `            y=a[j].v;`
31. ` `
32. `        dp[i]=max(x+y,dp[i-1]);`
33. `    }`
34. ` `
35. `    return dp[n-1];`
36. `}`
37. ` `
38. `int main()`
39. `{`
40. `    int i,n;`
41. `    cout<<"Enter the number of activities ";`
42. `    cin>>n;`
43. ` `
44. `    cout<<"Enter the start time, end time and value of each activity "<<endl;`
45. ` `
46. `    vector<activity> a(n);`
47. ` `
48. `    for(i=0;i<n;i++)`
49. `    {`
50. `        cin>>a[i].s>>a[i].e>>a[i].v;`
51. `    }`
52. ` `
53. `    cout<<"The maximum attainable value of activities is"<<endl;`
54. `    cout<<weightedActivity(n,a);`
55. ` `
56. `    cout<<endl;`
57. `    return 0;`
58. `}`
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

If you find any mistake above, kindly email to [email protected]