Coin change problem 1: Finding the minimum number of coins

The coin-change problem resembles the 0-1 Knapsack Problem in Dynamic Programming. It has two versions:

Finding the minimum number of coins, of certain denominations, required to make a given sum.
Finding the total number of possible ways a given sum can be made from a given set of coins.

Below is the solution to the first version of the problem.

The Problem

Assume that we are given a set of coins having the values {1, 3, 6}. To make a sum of 7 using these coins, all possible solutions are: {1,1,1,1,1,1,1}, {1,3,3}, and {1,6}. So the minimum number of coins required are 2, i.e. {1,6}. We reached our answer intuitively, but this wouldn’t work if there were too many denominations and a large sum was to be made.

Solution

One approach would be to generate all possible ways a sum can be made, and then choosing the one with the least number of coins. This, unlike Dynamic Programming, is computationally expensive.

Dividing into Subproblems

To implement Dynamic Programming, it is essential that you divide a problem into subproblems. We can view our problem as if we were to choose the better option from the following two options:

Selecting the highest possible coin: The subproblem is about making the amount (Sum - the coin we added) with the same set of coins.
Ignoring the highest possible coin: In this case, the subproblem is making the same sum with the original set of coins, minus the highest possible coin.

Choosing the better option in this problem equates to choosing the smaller of the two options. If the highest coin does not exceed the required sum, then we take the minimum of the two. Otherwise, we choose the second option and ignore the highest coin. Since that coin cannot be used in our solution, we act as if it doesn’t exist.

Recursive solution

The key part of a solution, when using DP, is to implement the array to keep track of the solutions to subproblems. This way, we won’t calculate what has already been done, again and again.

Each element of the 2-D array (arr) tells us the minimum number of coins required to make the sum j, considering the first i coins only.

Example

Supposing we have coins {1,5,6}. arr[2][15] = 3 means that we need at least 3 coins to make a sum of 15 if we only had the first 2 coins (i.e. {1,5}).

Following is the recursive solution to this problem:

if(coins[i] <= j){
    // Choosing the better of the two options:
    arr[i][j] = min(1 + arr[i][j - coins[i]], arr[i - 1][j]);
}
else{
    // Ignore the highest possible coin:
    arr[i][j] = arr[i - 1][j];
}

#include <iostream>
#include <limits.h> 
using namespace std;
double findMin(double a, double b){
    if(a <= b)
        return a;
    else
        return b;
}
int findMinCoins(int coins[], int sum, int size){
    // Declaring 2-D array to store solutions to sub-problems:
    double** arr = new double*[size + 1];
    for(int i = 0; i < size + 1; i++)
        arr[i] = new double[sum + 1];
    
    // Initialising first column to zero
    // because a sum of zero is made with no coins:
    for(int i = 0; i < size + 1; i++)
        arr[i][0] = 0;
    
    // Initialising first row to INT_MAX (undefined)
    // because a sum cannot be made with zero coins:
    for(int j = 0; j < sum + 1; j++)
        arr[0][j] = INT_MAX;
    
    // Applying the recursive solution:
    for(int i = 1; i < size + 1; i++){
        for(int j = 1; j < sum + 1; j++){
            if(coins[i - 1] > j)  // cannot pick the highest coin:
                arr[i][j] = arr[i - 1][j];
            else  // choosing the best option:
                arr[i][j] = findMin(1 + arr[i][j - coins[i - 1]], arr[i - 1][j]);
        }
    }
    
    // Storing final answer:
    int answer = arr[size][sum];
    
    // Freeing up the memory from heap:
    for(int i = 0; i < size + 1; i++)
        delete[] arr[i];
    delete[] arr;
    
    return answer;
}
int main(){
    int coins[] = {5, 7, 8, 9};
    int sum = 49;
    
    // Finding total number of available coins:
    int size = sizeof(coins) / sizeof(coins[0]);
    
    cout << "At least " << findMinCoins(coins, sum, size) <<
    " coins are required to make a value of " << sum << endl;
    
    return 0;
}