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.

```
#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.

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

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

Related Posts:

Recommended Articles: