Making Change Problem using Dynamic Programming

This is a C++ Program that Solves Change Making Problem using Dynamic Programming technique.

Problem Description

There are infinite number of coins of n different values. These values are given. Using these coins, you have to make change for Rs. Sum. Find the minimum number of coins required to change Rs. Sum.

Note that the problem is different from coin change problem. In coin change problem, we were asked to find out in how many ways the change can be made. In this problem, we are supposed to find out the minimum number of coins required to change.

Problem Solution

We will solving this problem in bottom up manner. We will first calculate the result for smaller value of sum and store the result in a matrix and use the stored values to compute results for higher value of sum.

Expected Input and Output

Case-1:

Sum=11
n=4
coin[]={1,5,6,8}
 
Expected result=2 
using 5 and 6

Program/Source Code

Here is source code of the C++ Program to Solve Change Making Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

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

```
#include<iostream>
```
```
#include<algorithm>
```
```
#include<climits>
```
```
using namespace std;
```
```
 
```

int changeMaking(int coin[], int n, int sum)

```
{
```
```
    int i,j;
```
```
    int x,y;
```
```
 
```
```
    //matrix to tabulate results
```
```
    int dp[n+1][sum+1];
```
```
 
```

    //dp[i][j]=minimum no. of coins required to change j using only i coins

```
 
```
```
    //initialization
```

    //if there is no coin, then infinite no. of coins will be required to change j

```
    for(j=0;j<=sum;j++)
```
```
        dp[0][j]=INT_MAX;
```
```
 
```

    //if value to be changed is 0, then no coin is required

```
    for(i=1;i<=n;i++)
```
```
        dp[i][0]=0;
```
```
 
```

    //i represents the number of coins being used

```
    for(i=1;i<=n;i++)
```
```
    {
```

        //j represents the amount whose change is required

```
        for(j=1;j<=sum;j++)
```
```
        {
```

            //if the value of current coin is less than or equal to the amount whose change is required, then first include the coin and then exclude the coin

            //compare both the results and select the one which takes minimum no. of coins

```
            if(j>=coin[i-1])
```
```
            {
```

                //without including the current coin

```
                x=dp[i-1][j];
```
```
 
```

                //the current coin is included(hence 1+)

```
                y=1+dp[i][j-coin[i-1]];
```
```
 
```

                //the lesser value out of both is taken

```
                dp[i][j]=min(x,y);
```
```
            }
```
```
 
```

            //If value of current coin is greater than the amount, this coin can not be included

```
            else
```
```
                dp[i][j]=dp[i-1][j];
```
```
        }
```
```
 
```
```
    }
```
```
 
```
```
    return dp[n][sum];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i;
```
```
    int n,sum;
```
```
 
```

    cout<<"Enter the amount whose change is required"<<endl;

```
    cin>>sum;
```
```
 
```

    cout<<"Enter the number of coins available"<<endl;

```
    cin>>n;
```
```
 
```
```
    int coin[n];
```
```
 
```

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

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

    cout<<"The least number of coins whose sum is equal to required sum is"<<endl;

```
    cout<<changeMaking(coin,n,sum);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the amount of change required, number of coins available and the value of coins. We pass these values to the function changeMaking as parameters. This function will calculate the expected result and return it. The returned value will be displayed.

Check this: Design & Analysis of Algorithms MCQ | Programming MCQs

Runtime Test Cases

 
Case-1:
$ g++ change_making.cpp
$ ./a.out
Enter the amount whose change is required
11
Enter the number of coins available
4
Enter the values of coins
1
5
6
8
The least number of coins whose sum is equal to required sum is
2

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

« Prev - Kadane’s Algorithm using Dynamic Programming

» Next - Longest Increasing Subsequence using Dynamic Programming

Next Steps:

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

Related Posts:

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

Recommended Articles: