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.

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:

Free Java Certification BootCamp is Live. Join Now!

 
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.

```
 
```
```
//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;
```
```
}
```

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.

« Prev - Assignments Problem – Dynamic Programming Solutions

Related Posts:

Recommended Articles: