In [1]:
from jupyterthemes import get_themes
from jupyterthemes.stylefx import set_nb_theme
themes = get_themes()
set_nb_theme(themes[1])
Out[1]:
In [2]:
%load_ext watermark
%watermark -a 'Ethen' -d -t -v -p jupyterthemes
Following the online book, Problem Solving with Algorithms and Data Structures. Chapter 4 discusses recursion.
Is a method of breaking problems down into smaller and smaller sub-problems until we get to a problem small enough that it can be solved trivially. Recursion must follow three important laws.
The first problem will be Converting an Integer to a String in Any Base.
In [3]:
def to_str(n, base):
convert_str = '0123456789ABCDEF'
if n < base:
# look up the string representation if it's smaller than the base
return convert_str[n]
else:
# convert_str comes after to to_str method so that it will
# delayed the addition until the recursive call finishes
return to_str(n // base, base) + convert_str[n % base]
print(to_str(769, 10))
print(to_str(1453, 16))
Changing money is an optimization problem involves making change using the fewest coins. e.g. The answer for making a change for 63 cents will be 6 coins: two quarters, one dime, and three pennies. How did we arrive at the answer of six coins? Well, one approach will be using a greedy method. Meaning we start with the largest coin in our arsenal (a quarter) and use as many of those as possible, then we go to the next lowest coin value and use as many of those as possible and keep going until we've arrived at our solution. This first approach is called a greedy method because we try to solve as big a piece of the problem as possible right away.
In [4]:
def change_money_greedy(amount, coin_values):
"""
using greedy algorithm to solve the minimum
number of coins needed to make change for the input
amount (an integer), given the all the possible coin values.
The coin values has to be sorted in
decreasing order for this code to work properly
"""
# key = coin_values
# value = corresponding number of that coin value
change = {}
for d in coin_values:
n_coins = amount // d
change[d] = n_coins
amount = amount % d
if not amount:
break
return change
In [5]:
amount = 63
coin_values = [25, 10, 5, 1]
change = change_money_greedy(amount, coin_values)
print(change)
The greedy method works fine when we are using U.S. coins, but suppose, in addition to the usual 1, 5, 10, and 25 cent coins we now have a 21 cent coin. In this instance our greedy method fails to find the optimal solution for 63 cents in change. With the addition of the 21 cent coin the greedy method would still find the solution to be 6 coins when the optimal answer should be 3 21 cent pieces.
Let’s look at a method called dynamic programming, where we could be sure that we would find the optimal answer to the problem. Dynamic programming solution is going to start with making change for one cent and systematically work its way up to the amount of change we require. This guarantees us that at each step of the algorithm we already know the minimum number of coins needed to make change for any smaller amount.
Let’s look at how we would fill in a table of minimum coins to use in making change for 11 cents. The following figure illustrates the process.
We start with one cent. The only solution possible up till this point is one coin (a penny). The next row shows the minimum for one cent and two cents. Again, the only solution is two pennies. The fifth row is where things get interesting. Now we have two options to consider, five pennies or one nickel. How do we decide which is best? We consult the table and see that the number of coins needed to make change for four cents is four, plus one more penny to make five, equals five coins. Or we can look at zero cents plus one more nickel to make five cents equals 1 coin. Since the minimum of one and five is one we store 1 in the table. Fast forward again to the end of the table and consider 11 cents. The three options that we have to consider:
Either option 1 or 3 will give us a total of two coins which is the minimum number of coins for 11 cents.
In [6]:
import numpy as np
from collections import defaultdict
def change_money_dp(amount, coin_values):
"""
using dynamic programming to solve
the minimum number of coins needed to make change for the
input amount (an integer), given the all the possible coin values.
unlike the greedy algorithm the coin values doesn't need to be sorted in
decreasing order for this code to work properly
"""
# index starts at 0 (change 0 essentially means nothing
min_coin = np.zeros(amount + 1, dtype = np.int)
used_coin = np.zeros(amount + 1, dtype = np.int)
for cents in range(amount + 1):
# all the coins that are smaller than the
# current change are all candidates for exchanging
possible_choices = [c for c in coin_values if c <= cents]
# store the minimum change number 1, and
# the maximum number of coins required to
# make change for the current `cents`,
# these will later be compared and updated
coin = 1
coin_count = cents
# consider using all possible coins to make
# change for the amount specified by cents,
# and store the minimum number to min_coins
for j in possible_choices:
# access the minimum coin required to make
# cents - j amount and add 1 to account for
# the fact that you're using the current coin
# to give the changes
min_coin_count = min_coin[cents - j] + 1
if min_coin_count < coin_count:
coin_count = min_coin_count
coin = j
min_coin[cents] = coin_count
used_coin[cents] = coin
# determine the number of each coins used to
# make the change
change = defaultdict(int)
coin = amount
while coin > 0:
coin_current = used_coin[coin]
coin -= coin_current
change[coin_current] += 1
return change
In [7]:
amount = 63
coin_values = [21, 10, 35, 5, 1]
change = change_money_dp(amount, coin_values)
print(change)
The following blog has a nice introduction on this topic. Blog: Dynamic Programming: Knapsack Optimization
In [8]:
def knapsack(value_weight, capacity):
"""0/1 knapsack problem"""
# construct the dynamic programming table, where each row represents
# the current capacity level and each column represents the item
n_items = len(value_weight)
# the padding (0, 1) tuple represents no padding at the beginning of both
# dimension and pad 1 value at the end of the dimension
# https://stackoverflow.com/questions/35751306/python-how-to-pad-numpy-array-with-zeros
table = np.pad(np.zeros((capacity, n_items)), (0, 1), 'constant').astype(np.int)
for j in range(1, n_items + 1):
value, weight = value_weight[j - 1]
for i in range(1, capacity + 1):
# if the current item's weight is
# larger than the capacity, then
# all we can do is lookup the maximum
# value of the previous column, i.e.
# best value at this capacity with previously
# seen items
if weight > i:
table[i, j] = table[i, j - 1]
else:
# if we can fit the item in, then we compare adding this new
# item's value with the capacity level just enough to add this
# value in
table[i, j] = max(table[i, j - 1], table[i - weight, j - 1] + value)
return table
In [9]:
capacity = 11
value_weight = [(8, 4), (4, 3), (10, 5), (15, 8)]
table = knapsack(value_weight, capacity)
print('max value:', table[capacity, len(value_weight)])
table
Out[9]:
In [10]:
# to see which items were taken (put in the knapsack),
# we check whether the row corresponding to the capacity
# we have remaining to use is different in the current
# column and the one before it, if it is, that means
# that item was chosen
remaining = capacity
items_taken = np.zeros(len(value_weight), dtype = np.bool)
for j in range(len(value_weight), 0, -1):
if table[remaining, j] != table[remaining, j - 1]:
items_taken[j - 1] = True
_, weight = value_weight[j - 1]
remaining -= weight
items_taken
Out[10]: