/*********************************************************************
* 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);
}
}
