This is a C++ Program that Solves Treats for the cows Problem using Dynamic Programming technique.
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.
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.
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
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;
}
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.
#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;
}
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.
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.
- Practice Computer Science MCQs
- Check Computer Science Books
- Practice Programming MCQs
- Apply for Computer Science Internship
- Check Data Structure Books