#=======================================================================
# 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]
#=======================================================================
# return makeExactChange(numberOfCoinsPerSubtotal(t, coins), t);
def subsetSumOfCoins( coins, t ) :
C = numberOfCoinsPerSubtotal( t, coins )
return makeExactChange( C, t )
#======================================================================
# Compute the number of coins in each subtotal amount of money
# from 0 to t.
#======================================================================
from sys import maxint
def numberOfCoinsPerSubtotal( t, coins ):
C = [maxint] * ( t + 1 )
C[0] = 0 # base case
for coin in coins:
for subtotal in range( 1, t + 1 ):
if coin <= subtotal and 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].
#======================================================================
def makeExactChange( C, t ):
result = []
while 0 < C[t]:
big = t
while C[big] <= C[t]:
t -= 1
result.append( big - t )
return result;
import unittest
from dynamic_programming import SubsetSum as algorithm
class Test( unittest.TestCase ):
def testSubsetSumOfCoins( self ):
coin = [1, 5, 10, 25]
t = 167
expResult = [1, 1, 5, 10, 25, 25, 25, 25, 25, 25]
result = algorithm.subsetSumOfCoins( coin, t )
self.assertEquals( expResult, result )
