Blueberries Problem – Dynamic Programming Solutions

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

Problem Description

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.

Problem Solution

This problem is quite similar to 0/1 knapsack problem with additional constraints of not being able to pick adjacent bushes.

advertisement
advertisement

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.

Expected Input and Output

Case-1:

 
number of bushes=5
limit=100
 
Blueberries in each bush=50 10 20 30 40
 
Expected Result=90

Case-2:

Note: Join free Sanfoundry classes at Telegram or Youtube
 
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
Program/Source Code

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.

advertisement
  1.  
  2. //blueberries
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6.  
  7. int main()
  8. {
  9.     int n,k;
  10.     int i,j;
  11.  
  12.     cout<<"Enter the number of bushes and limit of collecting blueberries"<<endl;
  13.     cin>>n>>k;
  14.  
  15.     //array to store number of blueberries in each bush
  16.     vector<int> a(n);
  17.  
  18.     //matrix for memoization
  19.     vector<vector<int> > dp(n+1,vector<int>(k+1,0));
  20.  
  21.     //dp[i][j]=max. attainable value with available i bushes, and limit j
  22.  
  23.     cout<<"Enter the number of blueberries in each bush "<<endl;
  24.     for(i=0;i<n;i++)
  25.         cin>>a[i];
  26.  
  27.     //for zero limit, max. attainable value is zero
  28.     for(i=0;i<=n;i++)
  29.     {
  30.         dp[i][0]=0;
  31.     }
  32.  
  33.     //for zero items, max. attainable value is zero
  34.     for(i=0;i<=k;i++)
  35.     {
  36.         dp[0][i]=0;
  37.     }
  38.  
  39.     //for i==1
  40.     for(j=a[0];j<=k;j++)
  41.     {
  42.        dp[1][j]=a[0]; 
  43.     }
  44.  
  45.     for(i=2;i<=n;i++)
  46.     {
  47.         for(j=1;j<=k;j++)
  48.         {
  49.             if(a[i-1]<=j)
  50.             {
  51.                 dp[i][j]=max(dp[i-1][j],a[i-1]+dp[i-2][j-a[i-1]]);
  52.             }
  53.  
  54.             else
  55.             {
  56.                 dp[i][j]=dp[i-1][j];
  57.             }
  58.         }
  59.     }
  60.  
  61.     cout<<"Maximum number of blueberries that can be collected is "<<endl;
  62.     cout<<dp[n][k]<<endl;
  63.  
  64.     return 0;
  65. }
Program Explanation

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.

Runtime Test Cases
 
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.

advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.