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


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!
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<climits>
  4. using namespace std;
  6. int changeMaking(int coin[], int n, int sum)
  7. {
  8.     int i,j;
  9.     int x,y;
  11.     //matrix to tabulate results
  12.     int dp[n+1][sum+1];
  14.     //dp[i][j]=minimum no. of coins required to change j using only i coins
  16.     //initialization
  17.     //if there is no coin, then infinite no. of coins will be required to change j 
  18.     for(j=0;j<=sum;j++)
  19.         dp[0][j]=INT_MAX;
  21.     //if value to be changed is 0, then no coin is required 
  22.     for(i=1;i<=n;i++)
  23.         dp[i][0]=0;
  25.     //i represents the number of coins being used
  26.     for(i=1;i<=n;i++)
  27.     {
  28.         //j represents the amount whose change is required
  29.         for(j=1;j<=sum;j++)
  30.         {
  31.             //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
  32.             //compare both the results and select the one which takes minimum no. of coins
  33.             if(j>=coin[i-1])
  34.             {
  35.                 //without including the current coin
  36.                 x=dp[i-1][j];
  38.                 //the current coin is included(hence 1+)
  39.                 y=1+dp[i][j-coin[i-1]];
  41.                 //the lesser value out of both is taken
  42.                 dp[i][j]=min(x,y);
  43.             }
  45.             //If value of current coin is greater than the amount, this coin can not be included
  46.             else
  47.                 dp[i][j]=dp[i-1][j];
  48.         }
  50.     }
  52.     return dp[n][sum];
  53. }
  55. int main()
  56. {
  57.     int i;
  58.     int n,sum;
  60.     cout<<"Enter the amount whose change is required"<<endl;
  61.     cin>>sum;
  63.     cout<<"Enter the number of coins available"<<endl;
  64.     cin>>n;
  66.     int coin[n];
  68.     cout<<"Enter the values of coins"<<endl;
  69.     for(i=0;i<n;i++)
  70.         cin>>coin[i];
  72.     cout<<"The least number of coins whose sum is equal to required sum is"<<endl;
  73.     cout<<changeMaking(coin,n,sum);
  75.     cout<<endl;
  76.     return 0;
  77. }
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.

Runtime Test Cases
$ g++ change_making.cpp
$ ./a.out
Enter the amount whose change is required
Enter the number of coins available
Enter the values of coins
The least number of coins whose sum is equal to required sum is

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


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.