Change Making Combinations Problem : Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4.
For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

Similar to previous problem we will fill a row F[n] which will have all the possible combinations.
We define F[0] here to 1. The logic is simple- we will select one coin and minus it to the required amount.

public class NoOfChangeMakingCombinations {

	public static int getChangeMakingCombinations(int coins[], int amount) {
		int[] F = new int[amount + 1];
		F[0] = 1;
		for (int i = 0; i < coins.length; i++){
			for (int j = coins[i]; j <= amount; j++){
				F[j] = F[j] + F[j - coins[i]];// pick one coin
			}
		}

		return F[amount];
	}
	
	public static void main(String[] args) {
		int[] A = { 5, 3, 2, 7 };
		System.out.println(NoOfChangeMakingCombinations.getChangeMakingCombinations(A, 7));
	}
}
Output
-------
3

Minimum Coin Change Problem : Give change for amount n using the minimum number of coins of denominations d1 < d2 < …..dm. Let F[n] be the minimum number of coins needed to make change for n cents. Let x be the value of the first coin used in the optimal solution. Then F[n] = 1 + C[n − x] .The amount n can only be obtained by adding one coin of denomination d[j] to the amount n−d[j] for j = 1, 2, . . . , m such that d[j]<=n . We will consider all possible denomination (d) and select the one which minimizing F(n-d[j]) + 1. Hence the recurrence will be- F[n] = {min,j:d[j]<=n{C[n-d[j]]+1}} if n>= 0
F[0] = 0

Algorithm

public class MinimumCoinChange {

    public static int getChange(int coins[], int amount) {
        int[] F = new int[amount + 1]; // table to fill minimum number of coins
        F[0] = 0;
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            int j = 0;
            while (j < coins.length && i >= coins[j]) {
                min = minimum(F[i - coins[j]], min);
                j++;
            }
            F[i] = min + 1;// add 1 coins
        }
        return F[amount];
    }

    private static int minimum(int i, int j) {
        return i < j ? i : j;
    }

    public static void main(String[] args) {
        int[] A = { 1, 2, 3 };
        System.out.println(getChange(A, 4));
    }
}

Let’s trace the algorithm

F[4] will have the final value.

Go to the next page – Click on the below red circle with page number.