Dynamic Programming

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
minimum-coin-change

F[4] will have the final value.

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

1
Leave a Reply

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
jimbet Recent comment authors

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
newest oldest most voted
Notify of
jimbet
Guest

hey thanks for the knowledge, but I think you might put the same table picture two times in coin row problem explaination.