6

[SOLVED] Money Exchange Problem Using C++

 2 years ago
source link: https://www.journaldev.com/61065/money-exchange-problem-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

In today’s article, we will learn to solve the money exchange problem using C++. It is a very popular software interview problem. You can expect the top recruiters to ask about this problem during an interview. In this article, we will learn the concept to solve this problem. One can solve this problem using two different strategies, i.e. using the greedy or the dynamic programming approach.

Problem Statement

You have a set of coins of different values. What is the minimum number of coins you would use to change a given value using these coins? Assume that you have an infinite supply of all the coins.

For example,

Coins: [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
Testcase 1: value = 137
Answer: 5
Testcase 2: value = 15
Answer: 2
Testcase 3: value = 7
Answer: 2
Coins: [1, 7, 10]
Testcase 1: value = 14
Answer: 2
Testcase 2: 24
Answer: 3
Example

Concept of the Money Exchange Problem

If you carefully notice, you will find that the greedy approach is not valid for the set: [1, 7, 10]. Hence we would only discuss the dynamic programming solution. Dynamic programming is nothing but optimization of the recursive formulation. We will follow the following instructions while writing the algorithm.

  • The recursive formulation will consider all the possible cases
  • For every case, we have the following recursive relation
    • f(N) = min(f(N - coins[i])), where ‘i’ ranges from 0 to size(coins)
  • It indicates that you can not pick a coin whose value is greater than N
  • As there’s only one variable to determine the total number of states, we will only use a one-dimensional array to store these states
  • The bottom-up approach is as follows.
    • Initialize a dynamic programming array of size N + 1 with INT_MAX
    • To exchange zero, you need not use any coins.
    • Start a for loop, from i = 1 to i = N
      • arr[i] = min(arr[i - coins[j]]), where j varies from j = 0 to j = size(coins)
    • Once you are out of this loop, just return arr[N]

Algorithm to Solve The Money Exchange Problem

int min_coins_bottom_up(vector <int> coins, int N)
{
int len = coins.size();
vector <int> dp(N + 1, INT_MAX);
// to change 0, we need not use
// any coins
dp[0] = 0;
// start filling the array
// in a bottom-up manner
for(int i = 1; i <= N; i++)
for(int j = 0; j < len; j++)
if(i - coins[j] >= 0)
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
return dp[N];
}

Solving the Money Exchange Problem Using C++ Progam

Let’s now solve the money exchange problem that we algorithmically understand, using C++.

#include <iostream>
#include <climits>
#include <vector>
using namespace std;
// function to find the minimum number of coins needed
int min_coins_bottom_up(vector <int> coins, int N)
{
int len = coins.size();
// initialize the vector for bottom - up approach
vector <int> dp(N + 1, INT_MAX);
// to change 0, we need not use
// any coins
dp[0] = 0;
// start filling the array
// in a bottom-up manner
for(int i = 1; i <= N; i++)
for(int j = 0; j < len; j++)
// only consider the coins whose values
// are less than the current state
if(i - coins[j] >= 0)
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
// return the answer
return dp[N];
}
// driver function
int main()
{
cout << "Enter the coins, press -1 to stop" << endl;
// array to store the value of coins
vector <int> coins;
while(true)
{
int ele;
cin >> ele;
if(ele == -1)
break;
coins.push_back(ele);
}
cout << "Enter the amount to change" << endl;
int amount;
cin >> amount;
cout << "The minimum coins needed to change are: " << min_coins_bottom_up(coins, amount) <<endl;
return 0;
}
AlgorithmMinimum Coins Algorithm

Output

Minimum Coins OutputMinimum Coins Output

Conclusion

In this article, we learned to solve the money exchange problem using C++. We went through the problem statement, and later we understood the concept. In the end, we coded the algorithm and a driver program to check its working. Notice that for the last case in the output screenshot, the output is INT_MIN. It is so because there’s no possible combination for this particular denomination to make up to eight. That’s it for now, thanks for reading.

Further Readings

To learn more about recursion or dynamic programming, you can go through the following articles,

https://www.journaldev.com/56866/solving-0-n-knapsack-problem-in-cpp

https://www.journaldev.com/56918/0-1-knapsack-using-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK