Treats for the Cows - Dynamic Programming Solutions

This is a C++ Program that Solves Treats for the cows Problem using Dynamic Programming technique.

Problem Description

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time. The treats are interesting for many reasons: The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats. Like fine wines and delicious cheeses, the treats improve with age and command greater prices. The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000). Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a. Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally? The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

Problem Solution

In this problem, the value of treats becomes as high as its age. So, our approach will be to select treats of lower values in earlier days and preserve the treats of high values for later to fetch greater values. The matrix dp calculates the result of the result of subproblems to avoid recomputation.

Expected Input and Output

Case-1:

Number of treats=5
Values of treats=1 3 1 5 2
The maximum revenue that can be obtained by selling the treats is= 43

Program/Source Code For Recursive Solution

Here is source code of the C++ Program to Solve Treats for Cows using Recursion. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
typedef vector<int> vi;
```
```
typedef vector<vi> vvi;
```
```
 
```
```
 
```

int calc(vvi &dp,vi &a,int i, int j, int k)

```
{
```
```
    if(i>j)
```
```
        return 0;
```
```
 
```
```
    if(dp[i][j]!=-1)
```
```
        return dp[i][j];
```
```
 
```
```
    //now, calculate
```

    return dp[i][j]=max(calc(dp,a,i+1,j,k+1)+a[i]*k,calc(dp,a,i,j-1,k+1)+a[j]*k);

```
 
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n,i;
```

    cout<<"Enter the number of treats ";

```
    cin>>n;
```
```
    vector<int> a(n);
```
```
 
```

    cout<<"Enter the values of treats "<<endl;

```
    for(i=0;i<n;i++)
```
```
        cin>>a[i];
```
```
 
```

    vector<vector<int> > dp(n,vector<int>(n,-1));

    cout<<"The maximum revenue that can be obtained by selling the treats is "<<endl;

```
    cout<<calc(dp,a,0,n-1,1)<<endl;
```
```
 
```
```
    return 0;
```
```
}
```

Program/Source Code for DP solution

Here is source code of the C++ Program to solve Treats for the cows Problem using Dynamic Programming. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

Note: Join free Sanfoundry classes at Telegram or Youtube

```
 
```
```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
int solve(int n, vector<int> a)
```
```
{
```

    vector<vector<int> > dp(n, vector<int>(n));

```
    int i,j;
```
```
    int day;
```
```
 
```
```
    //initialization
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        dp[i][i]=n*a[i];
```
```
    }
```
```
 
```
```
    for(int len=2;len<=n;len++)
```
```
    {
```
```
        day=n-len+1;
```
```
 
```
```
        for(i=0;i<(n-len+1);i++)
```
```
        {
```
```
            j=i+len-1;
```
```
 
```

            dp[i][j]=max(day*a[i]+dp[i+1][j],dp[i][j-1]+day*a[j]);

```
        }
```
```
    }
```
```
 
```
```
    return dp[0][n-1];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n,i;
```

    cout<<"Enter the number of treats ";

```
    cin>>n;
```
```
    vector<int> a(n);
```
```
 
```

    cout<<"Enter the values of treats "<<endl;

```
    for(i=0;i<n;i++)
```
```
        cin>>a[i];
```
```
 
```

    cout<<"The maximum revenue that can be obtained by selling the treats is "<<endl;

```
    cout<<solve(n,a)<<endl;
```
```
 
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we take input for the number of treats and their values. This input is passed as arguments to the function solve. In the solve function, we created a matrix to memoize the result of subproblems. The final answer is returned and displayed.

Runtime Test Cases

 
Case-1:
$ g++ treats.cpp
$ ./a.out
Enter the number of treats 5
Enter the values of treats 
1 3 1 5 2
The maximum revenue that can be obtained by selling the treats is 
43

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

« Prev - Integer Knapsack Problem – Dynamic Programming Solutions

» Next - Weighted Activity Selection using Dynamic Programming

Related Posts:

Recommended Articles: