Maximum Value of Gifts Problem – Dynamic Programming Solutions

This is a C++ Program that Solves Maximum Value of Gifts Problem using Dynamic Programming technique.

Problem Description

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.

Problem Solution

There are two ways to reach colums (i,j), one from above and one from left. Choose the one which gives more value.

Expected Input and Output


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
Program/Source Code

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.

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  5. int maxGifts(int n, int m, vector<vector<int> > gifts)
  6. {
  7.     //vector to store results
  8.     vector<vector<int> > dp(n+1,vector<int>(m+1, 0));
  10.     //dp[i][j]=maximum attainable value of gifts for the matrix of rows i and columns j only
  12.     for(int i=1;i<=n;i++)
  13.     {
  14.         for(int j=1;j<=m;j++)
  15.         {
  16.             //There are two ways to reach colums (i,j)
  17.             //one from above and one from left
  18.             //choose the one which gives more value 
  19.             dp[i][j]=max(dp[i][j-1],dp[i-1][j])+gifts[i][j];
  20.         }
  22.     }
  24.     return dp[n][m];
  25. }
  27. int main()
  28. {
  29.     int n,m;
  30.     cout<<"Enter the number of rows and columns"<<endl;
  31.     cin>>n>>m;
  33.     vector<vector<int> > gifts(n+1,vector<int>(m+1));
  35.     cout<<"Enter the values of gifts in cells"<<endl;
  36.     for(int i=1;i<=n;i++)
  37.     {
  38.         for(int j=1;j<=m;j++)
  39.         {
  40.             cin>>gifts[i][j];
  41.         }
  42.     }
  44.     cout<<"maximum attainable value of gifts is "<<endl;
  45.     cout<<maxGifts(n,m,gifts);
  47.     cout<<endl;
  48.     return 0;
  49. }
Program Explanation

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.

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

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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.