This is a C++ Program that Solves Maximum Value of Gifts Problem using Dynamic Programming technique.
You are given a matrix of order n*m. Each cell of the matrix has a gift of certain value. Starting from the top-left cell, you have to reach the bottom-right cell of the matrix collecting gifts of the visited cells. But you can visit either the cell below the current cell or the cell to right of current cell. Determine the maximum value of gifts you can collect.
There are two ways to reach colums (i,j), one from above and one from left. Choose the one which gives more value.
Case-1:
rows,columns=(4,4) Values of gifts in cells 1 10 3 8 12 2 9 6 5 7 4 11 3 7 16 5 maximum attainable value of gifts=53
Here is source code of the C++ Program to Solve Maximum Value of Gifts Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
#include<vector>
using namespace std;
int maxGifts(int n, int m, vector<vector<int> > gifts)
{
//vector to store results
vector<vector<int> > dp(n+1,vector<int>(m+1, 0));
//dp[i][j]=maximum attainable value of gifts for the matrix of rows i and columns j only
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
//There are two ways to reach colums (i,j)
//one from above and one from left
//choose the one which gives more value
dp[i][j]=max(dp[i][j-1],dp[i-1][j])+gifts[i][j];
}
}
return dp[n][m];
}
int main()
{
int n,m;
cout<<"Enter the number of rows and columns"<<endl;
cin>>n>>m;
vector<vector<int> > gifts(n+1,vector<int>(m+1));
cout<<"Enter the values of gifts in cells"<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>gifts[i][j];
}
}
cout<<"maximum attainable value of gifts is "<<endl;
cout<<maxGifts(n,m,gifts);
cout<<endl;
return 0;
}
In the main function, we ask the user to input the values for number of rows and columns and values of gifts in each cell. We pass these values to the function maxGifts as parameters. This function will calculate the expected result and return it. The returned value will be displayed.
Case-1: $ g++ max_gifts.cpp $ ./a.out Enter the number of rows and columns 4 4 Enter the values of gifts in cells 1 10 3 8 12 2 9 6 5 7 4 11 3 7 16 5 maximum attainable value of gifts is 53
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 Programming MCQs
- Apply for Data Structure Internship
- Buy Data Structure Books
- Practice Design & Analysis of Algorithms MCQ