This is a C++ Program that Solves Boredom Problem using Dynamic Programming technique.
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.
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].
Case-1:
a[]={1, 2, 3} Expected answer=4 by collecting 1 and 3 (2 has to be deleted)
Case-2:
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
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;
}
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.
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.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Buy Computer Science Books
- Apply for Information Technology Internship
- Apply for Computer Science Internship
- Apply for Data Structure Internship
- Buy Data Structure Books