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

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

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.

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

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

 
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.

Free 30-Day C Certification Bootcamp is Live. Join Now!

« Prev - Longest Common Substring using Dynamic Programming

» Next - Maximum Product Cutting using Dynamic Programming

Related Posts:

Check Data Structure Books
Practice Programming MCQs
Apply for Computer Science Internship
Practice Design & Analysis of Algorithms MCQ
Check Programming Books

Recommended Articles: