Boredom Problem - Dynamic Programming Solutions

This is a C++ Program that Solves Boredom Problem using Dynamic Programming technique.

Problem Description

Alex doesn’t like boredom. That’s why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let’s denote it a[k]) and delete it, at that all elements equal to a[k] + 1 and a[k] - 1 also must be deleted from the sequence. That step brings ak points to the player.

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Problem Solution

The problem is to find the maximum points that can be collected with the given constraints. This can be solved with Dynamic Programming. First, we read all the values and group them.

For example – If the values are 2 1 3 4 2 3 4, we group all 1’s together, all 2’s together and so on. This way we will be able to find frequency of each number. In this example, If 2 is selected in the final solution, then its total contribution will be 4 (number*its frequency).

Now, we create a array dp[] to memoize values. dp[i]=maximum points that can be collection using only i distict values. We will proceed in bottom up manner- first calculating dp[1], dp[2], …, dp[n].

If there are n distinct values in the input, the answer will be given by dp[n].

Expected Input and Output

Case-1:

 
a[]={1, 2, 3}
Expected answer=4 by collecting 1 and 3 (2 has to be deleted)

Case-2:

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

 
a[]={1, 2, 1, 3, 2, 2, 2, 2, 3}
Expected answer=10 by collecting all 2's (1 and 3 will be deleted)

Case-3:

a[]={5, 3, 4, 2, 3, 7, 2}
Expected answer=18 by collecting 3, 5 and 7

Program/Source Code

Here is source code of the C++ Program to Boredom problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
 
```
```
//boredom dp
```
```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
int main()
```
```
{
```
```
    int i,j;
```
```
    int n;
```
```
    long long x,y;
```
```
 
```
```
    cout<<"How many values ?"<<endl;
```
```
    cin>>n;
```
```
 
```

    //map to store value and its frequency

```
    map<int,int> mp;
```
```
    map<int, int> :: iterator it;
```
```
 
```
```
    cout<<"Enter the values "<<endl;
```
```
 
```
```
    //input all values
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>j;
```
```
 
```
```
        if(mp.find(j)!=mp.end())
```
```
        {
```
```
            //increase frequency by 1
```
```
            mp[j]++;
```
```
        }
```
```
 
```
```
        else
```
```
        {
```
```
            mp[j]=1;
```
```
        }
```
```
    }
```
```
 
```
```
    n=mp.size();
```
```
 
```
```
    //array to memoize values 
```

    vector<pair<int,long long int> > dp(mp.size()+1);

```
 
```
```
    //initialize
```
```
    dp[0].first=0;
```
```
    dp[0].second=0;
```
```
 
```

    for(it=mp.begin(),i=1;it!=mp.end();i++,it++)

```
    {
```
```
        dp[i].first=it->first;
```
```
 
```
```
        x=it->first;
```
```
        y=it->second;
```
```
 
```
```
        dp[i].second=x*y;
```
```
    }
```
```
 
```

    //implement DP in bottom up manner

```
    for(i=2;i<=n;i++)
```
```
    {
```
```
        //select previous value
```
```
        j=i-1;
```
```
 
```

        if(dp[i].first==(dp[j].first+1))

```
        {
```
```
            j--;
```
```
        }
```
```
 
```
```
        //now add
```
```
        dp[i].second+=dp[j].second;
```
```
 
```
```
        //compare
```

        dp[i].second=max(dp[i].second,dp[i-1].second);

```
    }
```
```
 
```
```
    //result
```

    cout<<"The answer is "<<dp[n].second<<endl;

```
 
```
```
    return 0;
```
```
}
```

Program Explanation

main() – In the main function, we take the value of n(number of integers) and then input the array of size n. The result is displayed at the standard output.

Runtime Test Cases

 
Case-1:
$ g++ boredom.cpp
$ ./a.out
How many values ?
3
Enter the values 
1 2 3
The answer is 4
 
Case-2:
$ ./a.out
How many values ?
9
Enter the values 
1 2 1 3 2 2 2 2 3
The answer is 10
 
Case-3:
$ ./a.out
How many values ?
7
Enter the values 
5 3 4 2 3 7 2
The answer is 18

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Army Problem – Dynamic Programming Solutions

» Next - T-Primes Problem using Dynamic Programming

Related Posts:

Recommended Articles: