#
Subset Sum: Coin Exact Change

/********************************************************************* * Author: Isai Damier * Title: Subset Sum of Coins for Exact Change * Project: geekviewpoint * Package: algorithms * * Statement: * Given a set of coins, find the shortest sequence of coins that * adds up to a given total t. * * Time Complexity: O(n*t) * where n is the number of coins and t is the total to make change for. * * Sample Input: coin={1,5,10,25}; t=167 * Sample Output: [1, 1, 5, 10, 25, 25, 25, 25, 25, 25] * * Dynamic Programming Strategy: * * Our approach is to compute the number of coins in each subtotal * amount of money from 0 to t, inclusive. The technique is to * add coins to a previously found subtotal so to get the next * subtotal, until we solve for the minimum number of coins in t. * After that, we simply walk the list of subtotals to get the * exact change (you'll see). * * 0] Create an array N of size t+1: * The indices/keys of the array represent different subtotals. * And the element/value at each index represents the number of * coins that adds up to that given subtotal: * N[subtotal] = number of coins * 1] Initialize N to infinity: * Before any computation is performed, assume/pretend that each * subtotal takes an infinite number of coins to compute. We know * that's not true, but that's what we have to prove. * 2] Set N at index 0 to 0: * Recall that for the N array, each index represents a subtotal * and the element at that index represents the number of coins * that add up to that subtotal. Therefore, we can set N[0] to 0 * because we know for certain that it takes 0 coins to get 0 * amount of money (this is the anchor/base case). * * 3] For subtotals ranging from 1 to t, inclusive, do: * For each coin: * If coin <= subtotal and N[subtotal-coin]+1 < subtotal, then: * N[subtotal] = N[subtotal-coin]+1 * * Step 3 is known as the relaxation step. We started with an extreme * and unrealistic assumption (i.e. that it takes infinite number of * coins to make change for the money t), then we keep relaxing * our assumptions until we get to the truth. * * EXAMPLE: You should really skip the following manual example and go * straight to the code. Then, if you need help seeing how the code * is computing the number of coins for each subtotal, come back here. * * For t=10 and coins = {1,3,5}, the final version of N is: * * N[0] = 0; //base case : 0 coins for 0 cent * N[1] = N[0]+coins[0] = 0+1 = 1 : 1 coin for 1 cent {1} * N[2] = N[1]+coins[0] = 1+1 = 2 : 2 coins for 2 cents (1,1) * N[3] = coins[1] = 1 : 1 coin for 3 cents {3} * N[4] = N[1]+coins[1] = 1+1 = 2 : 2 coins for 4 cents (3,1) * N[5] = coins[2] = 1 : 1 coin for 5 cents {5} * N[6] = N[5]+coins[0] = 1+1 = 2 : 2 coins for 6 cents (5,1) * N[7] = N[6]+coins[0] = 2+1 = 3 : 3 coins for 7 cents (5,1,1) * N[8] = N[5]+coins[2] = 1+1 = 2 : 2 coins for 8 cents (5,3) * N[9] = N[8]+coins[0] = 2+1 = 3 : 3 coins for 9 cents (5,1,3) * N[10] = N[5]+coins[2] = 1+1 = 2 : 2 coins for 10 cents (5,5) ********************************************************************/ package algorithm.programming.dynamic; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class SubsetSum { /** * return makeExactChange(numberOfCoinsPerSubtotal(t, coins), t); **/ public List<Integer> subsetSumOfCoins(int[] coins, int t) { int[] C = numberOfCoinsPerSubtotal(t, coins); return makeExactChange(C, t); } /** * Compute the number of coins in each subtotal amount of money * from 0 to t. */ private int[] numberOfCoinsPerSubtotal(int t, int[] coins) { int[] C = new int[t + 1]; Arrays.fill(C, Integer.MAX_VALUE); C[0] = 0;// base case for (int coin : coins) { for (int subtotal = 1; subtotal <= t; subtotal++) { if (coin <= subtotal && C[subtotal] > C[subtotal - coin] + 1) { C[subtotal] = C[subtotal - coin] + 1; } } } return C; } /** * Now that we know how many coins it takes to get each subtotal * amount of money up to t, we can track the denomination of each coin: * keep subtracting the next subtotal that takes fewer coins than t. * For instance in the manual example above where t=10 and * coins = {1,3,5}; since t N[t=10] takes 2 coins, the next subtotal * that takes fewer coins than N[10] is N[5], and the next subtotal * that takes fewer coins than N[5] is N[0]. Hence the denominations * for N[10] are 10-5 and 5-0: {5,5}. **/ private List<Integer> makeExactChange(int[] C, int t) { List<Integer> result = new ArrayList<Integer>(); while (0 < C[t]) { int big = t; while (C[big] <= C[--t]); result.add(big - t); } return result; } }

package algorithm.programming.dynamic; import java.util.Arrays; import java.util.List; import static org.junit.Assert.*; import org.junit.Test; public class SubsetSumTest { /** * Test of subsetSumOfCoins method, of class SumOfCoins. */ @Test public void testSubsetSumOfCoins() { System.out.println("subsetSumOfCoins"); int[] coin = {1, 5, 10, 25}; int t = 167; SubsetSum instance = new SubsetSum(); List expResult = Arrays.asList(1, 1, 5, 10, 25, 25, 25, 25, 25, 25); List result = instance.subsetSumOfCoins(coin, t); assertEquals(expResult, result); } }