recursion.ipynb

Kernel: Python 3 (ipykernel)

Table of Contents

• 1  Recursion, Greedy Algorithm, Dynamic Programming
  • 1.1  Recursion
  • 1.2  Greedy Algorithm
  • 1.3  Dynamic Programming - Changing Coin
  • 1.4  Dynamic Programming - 0/1 Knapsack

from jupyterthemes import get_themes
from jupyterthemes.stylefx import set_nb_theme
themes = get_themes()
set_nb_theme(themes[1])

%load_ext watermark
%watermark -a 'Ethen' -d -t -v -p jupyterthemes

Ethen 2017-10-16 21:23:45 

CPython 3.5.2
IPython 6.2.1

jupyterthemes 0.15.0

Recursion, Greedy Algorithm, Dynamic Programming

Following the online book, Problem Solving with Algorithms and Data Structures. Chapter 5 discusses recursion.

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.

• It must have a base case

• It must call itself recursively

• It must change it's state and move towards the base case

The first problem will be Converting an Integer to a String in Any Base.

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))

769
5AD

Greedy Algorithm

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.

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

amount = 63
coin_values = [25, 10, 5, 1]
change = change_money_greedy(amount, coin_values)
print(change)

{25: 2, 10: 1, 5: 0, 1: 3}

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.

Dynamic Programming - Changing Coin

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:

• A penny plus the minimum number of coins to make change for 11−1=10 cents (1)

• A nickel plus the minimum number of coins to make change for 11−5=6 cents (2)

• A dime plus the minimum number of coins to make change for 11−10=1 cent (1)

Either option 1 or 3 will give us a total of two coins which is the minimum number of coins for 11 cents.

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

amount = 63
coin_values = [21, 10, 35, 5, 1]
change = change_money_dp(amount, coin_values)
print(change)

defaultdict(<class 'int'>, {21: 3})

Dynamic Programming - 0/1 Knapsack

The following blog has a nice introduction on this topic. Blog: Dynamic Programming: Knapsack Optimization

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

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

max value: 19

array([[ 0,  0,  0,  0,  0],
       [ 0,  0,  0,  0,  0],
       [ 0,  0,  0,  0,  0],
       [ 0,  0,  4,  4,  4],
       [ 0,  8,  8,  8,  8],
       [ 0,  8,  8, 10, 10],
       [ 0,  8,  8, 10, 10],
       [ 0,  8, 12, 12, 12],
       [ 0,  8, 12, 14, 15],
       [ 0,  8, 12, 18, 18],
       [ 0,  8, 12, 18, 18],
       [ 0,  8, 12, 18, 19]])

# 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

array([False,  True, False,  True], dtype=bool)