Q: Given pennies, nickels, dimes, and quarters, and a certain money value $v$, make the total value $v$ with the fewest total coins possible.
This is a famous introductory exercise.
The brute force solution is to iterate over every possible combination of coins whose total is smaller than the value $v$, appending coins of each type to the prior total and checking if the result is equal in value to $v$.
import unittest
class TestCC(unittest.TestCase):
"""Example of how to use unittest in Jupyter."""
def testZeroLength(self):
self.assertEqual(cc(0, []), [])
def testTrivial(self):
self.assertEqual(cc(1, [1]), [1])
def testDouble(self):
self.assertEqual(cc(1, [1, 1]), [1])
def testNonTrivial(self):
self.assertEqual(sorted(cc(5, [1, 2, 3])), [2, 3])
def testNonTrivialMore(self):
self.assertEqual(sorted(cc(6, [1, 2, 3, 4])), [2, 4])
def testImpossible(self):
self.assertEqual(sorted(cc(1, [10])), [])
if __name__ == '__main__':
unittest.main(argv=[''], exit=False)
......
4 {3: [3], 2: [2], 1: [1]} [3] 5 {4: [3, 1], 3: [3], 2: [2]} [3] 5 {4: [4], 3: [3], 2: [2], 1: [1]} [4] 6 {5: [4, 1], 4: [4], 3: [3], 2: [2]} [4]
---------------------------------------------------------------------- Ran 6 tests in 0.007s OK
function cc(v, coins):
known_solutions = []
rcc(known_solutions)
return argmin(known_solutions)
function rcc(v, coins, known_solutions, prior_coins):
for coin in coins:
next_v = prior.value + coin.value
if next_v = v:
known_solutions.append(next_v)
break
else if next_v > v:
break
else:
new_prior = prior_coins.push(coin)
rcc(v, coins, known_solutions, new_prior)
def cc(v, coins):
known_solutions = []
start_prior = {'value': 0, 'coins': []}
rcc(v, coins, known_solutions, start_prior)
if known_solutions == []:
return []
best_solution = known_solutions[0]
for solution in known_solutions:
if len(solution) < len(best_solution):
best_solution = solution
return best_solution
def rcc(v, coins, known_solutions, prior_coins):
for coin in coins:
next_v = prior_coins['value'] + coin
if next_v == v:
known_solutions.append(prior_coins['coins'] + [coin])
break
elif next_v > v:
break
else:
new_prior = {'value': next_v, 'coins': prior_coins['coins'] + [coin]}
rcc(v, coins, known_solutions, new_prior)
It turns out that an optimal solution to the coin change problem is to just take as many of the largest donomination of coin as possible, and working up the list. There is a recursive proof you can do to show that this is true.
function cc(v, coins):
sol = []
sol_tot = 0
for coin in coins:
while (sol_tot + coin <= v):
sol.append(coin)
sol_tot += coin
if sol_tot == v:
return sol_tot
return None
def cc(v, coins):
sol = []
sol_tot = 0
for coin in coins:
while (sol_tot + coin <= v):
sol.append(coin)
sol_tot += coin
if sol_tot == v:
return sol
return None
cc(5, [3, 2, 1])
[3, 2]
The other solution is to recognize that the optimal solution for value $x$ is the best (smallest) solution amongst $x - 1$, $x - 5$, $x - 10$, and $x - 25$, plus one (the one additional coin required). In other words:
$$\text{cc}(x) = \min{\{\text{cc}(x-10), \text{cc}(x-5), \text{cc}(x-25), \text{cc}(x-1)\}} + 1$$We can use this relation to forward solve the problem.
function cc(v, coins):
memo = {coin: [coin] for coin in coins}
for n in range(2, v + 1):
priors = [n - coin for coin in coins if n - coin >= 1]
priors = [memo[prior] for prior in priors]
selected_prior_idx = argmin([prior for prior in priors])
selected_prior = priors[selected_prior_idx]
selected_prior_missing_coin = coins[selected_prior_idx]
memo[n] = selected_prior + [selected_prior_missing_coin]
return memo[v]
def cc(v, coins):
if coins == [] or v < min(coins): return []
coins = sorted(coins)
memo = {coin: [coin] for coin in coins}
for n in range(2, v + 1):
# Skip keys already included. Missed this in the initial pseudocode!
if n in memo.keys():
continue
priors = [n - coin for coin in coins if n - coin >= 1]
priors = {prior: memo[prior] for prior in priors}
def argmin(d):
if len(d.keys()) == 0: return
best, best_idx = d[list(d.keys())[0]], 0
for (idx, d_k) in enumerate(d.keys()):
if len(d[d_k]) < len(best):
best, best_idx = d[d_k], idx
return best, best_idx
selected_prior, selected_prior_idx = argmin(priors)
print(n, priors, selected_prior)
selected_prior_missing_coin = coins[selected_prior_idx]
memo[n] = selected_prior + [selected_prior_missing_coin]
return memo[v]
After a long derivation looking at the recursion tree, I think the brute-force solution is perhaps $O(n!v!)$, where $n$ is the number of different coins possible and $v$ is the the value we are looking for, but it's hard to be sure from a time-constrained look at the numbers.
The greedy solution is $O(n)$, where $n$ is the number of coins.
The dynamic solution is $O(v)$, where $v$ is the value.