This is a C++ Program that Solves Blueberries Problem using Dynamic Programming technique.
Teresa wants to pick up the blueberries in such a way that she may not exceed the limit proposed.
When picking the blueberries, she noticed that if she pick from the bush i, she couldn’t pick the blueberries at the bush i+1 (some sort of magic in rainbowland).
Worried about this, Teresa wants to know the maximum blueberries she can pick, given the number of bushes and the number of blueberries in each bush.
Will contain an integer T, then, T cases will follow, each case starts with a number N and K, being N the number of bushes and K the number of blueberries Teresa will pick as maximum, the next line contains N integers, each one representing the blueberries there is on the i-th bush.
This problem is quite similar to 0/1 knapsack problem with additional constraints of not being able to pick adjacent bushes.
We will create a matrix dp[][], where dp[i][j]=maximum blueberries that can be collected from first i bushes with limit being j. We will fill this matrix row wise in a bottom up manner and ultimately report the answer.
Case-1:
number of bushes=5 limit=100 Blueberries in each bush=50 10 20 30 40 Expected Result=90
Case-2:
number of bushes=5 limit=87 Blueberries in each bush=21 45 30 12 14 Expected Result=65
Case-3:
number of bushes=4 limit=42 Blueberries in each bush=13 28 25 15 Expected Result=38
Here is source code of the C++ Program to Solve Blueberries problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
//blueberries
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
int i,j;
cout<<"Enter the number of bushes and limit of collecting blueberries"<<endl;
cin>>n>>k;
//array to store number of blueberries in each bush
vector<int> a(n);
//matrix for memoization
vector<vector<int> > dp(n+1,vector<int>(k+1,0));
//dp[i][j]=max. attainable value with available i bushes, and limit j
cout<<"Enter the number of blueberries in each bush "<<endl;
for(i=0;i<n;i++)
cin>>a[i];
//for zero limit, max. attainable value is zero
for(i=0;i<=n;i++)
{
dp[i][0]=0;
}
//for zero items, max. attainable value is zero
for(i=0;i<=k;i++)
{
dp[0][i]=0;
}
//for i==1
for(j=a[0];j<=k;j++)
{
dp[1][j]=a[0];
}
for(i=2;i<=n;i++)
{
for(j=1;j<=k;j++)
{
if(a[i-1]<=j)
{
dp[i][j]=max(dp[i-1][j],a[i-1]+dp[i-2][j-a[i-1]]);
}
else
{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<"Maximum number of blueberries that can be collected is "<<endl;
cout<<dp[n][k]<<endl;
return 0;
}
In the main function, we take input for number of bushes, limit and the number of blueberries in each bush. Then, we will fill the memoization matrix row wise and ultimately display the result on standard output.
Case-1: $ g++ blueberries.cpp $ ./a.out Enter the number of bushes and limit of collecting blueberries 5 100 Enter the number of blueberries in each bush 50 10 20 30 40 Maximum number of blueberries that can be collected is 90 Case-2: $ ./a.out Enter the number of bushes and limit of collecting blueberries 5 87 Enter the number of blueberries in each bush 21 45 30 12 14 Maximum number of blueberries that can be collected is 65 Case-3: $ ./a.out Enter the number of bushes and limit of collecting blueberries 4 42 Enter the number of blueberries in each bush 13 28 25 15 Maximum number of blueberries that can be collected is 38
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
- Apply for Information Technology Internship
- Practice Computer Science MCQs
- Practice Design & Analysis of Algorithms MCQ
- Practice Programming MCQs
- Buy Programming Books