1Brute-force algorithm¶
The find_min_coins_brute_force function takes as parameters
- the set of possible coins, C
- the amount to change, N
and returns the minimum number of coins required to change N.
The function uses recursion to extensively check all combinations and select the optimal one.
import sys
def find_min_coins_brute_force(C, curr_N):
if curr_N == 0:
return 0
min_coins = sys.maxsize
for c in C:
if c <= curr_N:
res = find_min_coins_brute_force(C, curr_N - c) + 1
min_coins = min(res, min_coins)
return min_coinsmin_coins = find_min_coins_brute_force([1, 4, 5], 41)
print("The minimum number of coins is", min_coins)The minimum number of coins is 9
2Dynamic programming algorithm¶
The find_min_coins_dynamic_programming takes as parameters
- the set of possible coins, C
- the amount to change, N
The function returns a list containing
- the minimum number of coins required to change N
- the dynamic programming table
- an optimal solution
The function uses the algorithm discussed in class, whereby a recursive relation is used to fill a table. The last entry of the table is the optimal solution, and then the table itself can be used to trace back the solution in terms of coins.
# recursive relation
def compute_w(table, x, c):
if x - c >= 0:
return table[x - c] + 1
else:
return sys.maxsize
# the first argument should be the set of possible coins, the second is the amount to change
def find_min_coins_dynamic_programming(C, N):
# fill in
table = [0, ] * (N + 1)
for x in range(1, N + 1):
table[x] = min([compute_w(table, x, c) for c in C])
# trace back
curr_x = N
S = []
while curr_x > 0:
to_find = table[curr_x] - 1
for c in C:
if curr_x - c >= 0 and table[curr_x - c] == to_find:
break
# some thing as above, but with a one-liner: perhaps less readable, but we avoid a python loop and a break
# c = list(filter(lambda c: curr_x - c >= 0 and table[curr_x - c] == to_find, C))[0]
S.append(c)
curr_x -= c
return table[-1], table, Smin_coins, table, S = find_min_coins_dynamic_programming([1, 4, 5], 15)
print("The minimum number of coins is", min_coins)
print("\nThe dynamic programming table is\n")
print("|", " | ".join(["{:2d}".format(x) for x in range(len(table))]), "|")
print("|" + "----|" * len(table))
print("|", " | ".join(["{:2d}".format(x) for x in table]), "|\n")
print("An optimal solution is:", S)The minimum number of coins is 3
The dynamic programming table is
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|
| 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 |
An optimal solution is: [5, 5, 5]
3A simple exercise¶
Find the time complexity of the two solutions in terms of the length of C and of the amount of money to change N. In order to do so, one option is to extend the following example
import time
bf_start_time = time.time()
find_min_coins_brute_force([1, 4, 5], 41)
bf_end_time = time.time()
dp_start_time = time.time()
find_min_coins_dynamic_programming([1, 4, 5], 41)
dp_end_time = time.time()
print(f"Brute force elapsed time: {bf_end_time - bf_start_time:.2f} s")
print(f"Dynamic programming elapsed time: {dp_end_time - dp_start_time:.2e} s")Brute force elapsed time: 6.19 s
Dynamic programming elapsed time: 1.19e-04 s