Dynamic Programming and Greedy Algorithms

Greedy algorithms

An optimisation problem asks for the best answer: the fewest coins, the shortest route, the highest value. A greedy algorithm builds the answer one step at a time and always takes the best looking choice right now, never going back to reconsider it.

Giving change

To give 68p in change, take the biggest coin that still fits, and repeat.

def greedy_change(amount, coins):
    given = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            given.append(coin)
            amount = amount - coin
    return given

uk = [1, 2, 5, 10, 20, 50]
print(greedy_change(68, uk))
print(len(greedy_change(68, uk)), "coins")

For British coins that gives the fewest coins every time. But greedy is only as good as the problem allows. Suppose a country has coins worth 1, 3 and 4, and you must give 6:

def greedy_change(amount, coins):
    given = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            given.append(coin)
            amount = amount - coin
    return given

print(greedy_change(6, [1, 3, 4]))     # 4 + 1 + 1
print("but 3 + 3 uses only two coins")

Greedy took the 4 because it looked best, and then it was stuck with two 1s. It never went back.

A greedy algorithm that is correct: choosing meetings

A room can host one meeting at a time. Given the start and end of every request, how can you fit in the most meetings? Taking the shortest meeting first fails. Taking the earliest start fails. The rule that works is to always take the meeting that finishes earliest, because it leaves the most room for the rest.

meetings = [("maths", 9, 11), ("art", 9, 10), ("history", 10, 12), ("science", 11, 13),
            ("music", 12, 14), ("drama", 13, 15)]

def most_meetings(meetings):
    chosen, free_from = [], 0
    for name, start, end in sorted(meetings, key=lambda m: m[2]):
        if start >= free_from:
            chosen.append(name)
            free_from = end
    return chosen

print(most_meetings(meetings))

Where greedy shows up

You have already met greedy algorithms. Dijkstra's algorithm always settles the closest unvisited vertex. Kruskal's and Prim's take the cheapest edge that is safe. Huffman coding, in the compression topic, always merges the two rarest symbols. In each, the greedy choice has been proved to be safe.

Dynamic programming

Dynamic programming (DP) solves a big problem by solving its smaller pieces first and remembering the answers, so no piece is ever solved twice. It applies when a problem has two features:

• Overlapping subproblems. The same smaller problem comes up again and again. (You saw this with fib(3) inside both fib(4) and fib(5).)
• Optimal substructure. The best answer to the big problem is built from the best answers to smaller ones.

The fewest coins, properly

Let best[a] be the fewest coins that make amount a. To make a, the last coin must be one of the coins, say c. Then what is left is a - c, and its best answer is already in the table. Try every coin and keep the smallest:

best[a] = 1 + min(best[a - c]) for every coin c with c <= a

def fewest_coins(amount, coins):
    best = [0] + [None] * amount
    for a in range(1, amount + 1):
        options = [best[a - c] + 1 for c in coins if c <= a and best[a - c] is not None]
        best[a] = min(options) if options else None
    return best

table = fewest_coins(10, [1, 3, 4])
for a, n in enumerate(table):
    print("amount", a, "needs", n, "coins")

This bottom-up method fills a table from the smallest amount upwards. Every entry takes only a few steps because the entries it needs are already there. It costs O(amount x number of coins), and it gets 6p right: two coins.

Top-down: recursion with memoisation

The same idea can be written as a recursive function with a cache, which is exactly the memoisation from the recursion topic. This is top-down: start from the question and only work out the sub-answers that are actually needed.

from functools import lru_cache

calls = 0

@lru_cache(maxsize=None)
def fewest(amount):
    global calls
    calls += 1
    if amount == 0:
        return 0
    options = [fewest(amount - c) + 1 for c in (1, 3, 4) if c <= amount]
    return min(options)

print(fewest(40), "coins for 40p, using", calls, "calls")

Without the cache, fewest(40) would make over 300 million calls. With it, each of the 41 amounts is worked out once.

Counting the ways

Dynamic programming can also count. How many different ways are there to make 10p from 1p, 2p and 5p coins? Let ways[a] be the number of ways to make a. Add the coins one kind at a time:

def count_ways(amount, coins):
    ways = [1] + [0] * amount          # one way to make 0: use nothing
    for coin in coins:
        for a in range(coin, amount + 1):
            ways[a] += ways[a - coin]
    return ways[amount]

print(count_ways(10, [1, 2, 5]))
print(count_ways(100, [1, 2, 5, 10, 20, 50]))

The knapsack problem

A hiker's bag can carry 50 kg. Each item has a weight and a value. Which items should go in to make the total value as high as possible without going over the weight limit? Each item is taken whole or left behind. This is the 0/1 knapsack problem, and a version of it hides inside loading lorries, choosing investments and cutting stock.

Greedy fails here

An obvious rule is to take the items with the best value for their weight first.

items = [("tent", 10, 60), ("stove", 20, 100), ("food", 30, 120)]    # name, kg, value
limit = 50

def greedy_by_ratio(items, limit):
    taken, weight, value = [], 0, 0
    for name, kg, worth in sorted(items, key=lambda i: i[2] / i[1], reverse=True):
        if weight + kg <= limit:
            taken.append(name)
            weight += kg
            value += worth
    return taken, value

print(greedy_by_ratio(items, limit))
print("but stove and food together are worth", 100 + 120, "and weigh", 20 + 30)

The dynamic programming table

Let table[i][w] be the best value using only the first i items with a bag that holds w. For item i there are two choices: leave it (the answer is the row above) or take it (its value, plus the best for the space that remains).

items = [("tent", 10, 60), ("stove", 20, 100), ("food", 30, 120)]
limit = 50

def knapsack(items, limit):
    table = [[0] * (limit + 1) for _ in range(len(items) + 1)]
    for i, (name, kg, worth) in enumerate(items, start=1):
        for w in range(limit + 1):
            table[i][w] = table[i - 1][w]                         # leave it
            if kg <= w:
                table[i][w] = max(table[i][w], table[i - 1][w - kg] + worth)   # take it
    # walk back up the table to see which items were taken
    taken, w = [], limit
    for i in range(len(items), 0, -1):
        if table[i][w] != table[i - 1][w]:
            name, kg, worth = items[i - 1]
            taken.append(name)
            w = w - kg
    return table[len(items)][limit], taken

print(knapsack(items, limit))

The table is filled once, row by row, so the cost is O(n x W) for n items and a limit of W. Compare it with trying every combination:

limit = 60

for n in (10, 20, 30, 40):
    print(n, "items: brute force", 2 ** n, "subsets, table", n * limit, "cells")

Strings: common subsequences and edit distance

Dynamic programming is at its best when comparing two sequences.

Longest common subsequence

A subsequence keeps letters in order but may skip some. The longest common subsequence (LCS) of AGGTAB and GXTXAYB is GTAB, four letters. Tools that compare two versions of a file, such as git diff, are built on this idea.

Let t[i][j] be the LCS length of the first i letters of one word and the first j of the other. If the next two letters match, extend the diagonal. If not, take the better of dropping a letter from either word.

def lcs(a, b):
    t = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                t[i][j] = t[i - 1][j - 1] + 1
            else:
                t[i][j] = max(t[i - 1][j], t[i][j - 1])
    # read the answer back out
    i, j, letters = len(a), len(b), []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            letters.append(a[i - 1])
            i, j = i - 1, j - 1
        elif t[i - 1][j] >= t[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(letters))

print(lcs("AGGTAB", "GXTXAYB"))

Edit distance

How different are two words? The edit distance (Levenshtein distance) is the fewest single letter insertions, deletions and substitutions that turn one into the other. kitten becomes sitting in three: k to s, e to i, and add g.

def edit_distance(a, b):
    d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        d[i][0] = i                       # delete every letter
    for j in range(len(b) + 1):
        d[0][j] = j                       # insert every letter
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            same = 0 if a[i - 1] == b[j - 1] else 1
            d[i][j] = min(d[i - 1][j] + 1,           # delete
                          d[i][j - 1] + 1,           # insert
                          d[i - 1][j - 1] + same)    # substitute, or keep if equal
    return d[len(a)][len(b)]

print(edit_distance("kitten", "sitting"))
print(edit_distance("python", "pyhton"))

A spell checker uses it to offer "did you mean": measure the distance from what was typed to every dictionary word and offer the closest.

def edit_distance(a, b):
    d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        d[i][0] = i
    for j in range(len(b) + 1):
        d[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            same = 0 if a[i - 1] == b[j - 1] else 1
            d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + same)
    return d[len(a)][len(b)]

dictionary = ["algorithm", "logarithm", "rhythm", "alright", "arithmetic"]

def did_you_mean(word):
    return min(dictionary, key=lambda w: (edit_distance(word, w), w))

for typed in ["algoritm", "arithmatic", "rythm"]:
    print(typed, "->", did_you_mean(typed))

Choosing a strategy

There is no single best way to solve a problem. The question to ask is what kind of problem is it?

Divide and conquer and dynamic programming look alike. The difference: merge sort splits a list into halves that never share anything, so there is nothing to remember. Fibonacci splits into pieces that overlap heavily, so remembering them is the whole point.

When even a table is not enough: the travelling salesperson

A delivery driver must visit every one of n towns and return home by the shortest route. The only known way that always finds the best route is, in effect, to check them all, and there are (n - 1)! routes.

import math

for n in (5, 8, 10, 15, 20, 25):
    print(n, "towns:", math.factorial(n - 1), "routes")

At 20 towns that is over a hundred quadrillion routes. No computer can check them in a lifetime, so real systems use a heuristic. The simplest is nearest neighbour: always drive to the closest town not yet visited. It is greedy, it is fast, and it is not always good.

import itertools
import math

towns = {"A": (0, 0), "B": (1, 5), "C": (4, 1), "D": (5, 6), "E": (8, 2), "F": (9, 7), "G": (3, 8)}

def length(route):
    pairs = zip(route, route[1:] + route[:1])
    return sum(math.dist(towns[a], towns[b]) for a, b in pairs)

def nearest_neighbour(start):
    route = [start]
    left = set(towns) - {start}
    while left:
        here = towns[route[-1]]
        route.append(min(left, key=lambda t: math.dist(here, towns[t])))
        left.remove(route[-1])
    return route

best = min((["A"] + list(p) for p in itertools.permutations(sorted(set(towns) - {"A"}))), key=length)
quick = nearest_neighbour("A")
print("best route    ", best, round(length(best), 1))
print("nearest first ", quick, round(length(quick), 1))

The shortcut found a route about a third longer than the best one. For a few towns you can afford to be exact. For hundreds you accept a good answer. Knowing which situation you are in, and being able to explain the trade, is the skill the examiner is looking for.

Key terms you must be able to define

Optimisation problem

A problem that asks for the best answer by some measure, such as the shortest, cheapest or highest value.

Greedy algorithm

An algorithm that makes the best looking choice at each step and never reconsiders it.

Heuristic

A practical shortcut that finds a good answer quickly but does not guarantee the best one.

Dynamic programming

Solving a problem by solving its overlapping smaller problems once each and storing the answers.

Overlapping subproblems

A property of a problem where the same smaller problem has to be solved many times.

Optimal substructure

A property where the best answer to a problem is built from the best answers to smaller versions of it.

Memoisation (top-down)

Recursion that stores each result when it is first worked out.

Tabulation (bottom-up)

Filling in a table from the smallest sub-problem upwards.

Knapsack problem

Choosing items of different weights and values to give the greatest value within a weight limit.

Edit distance

The fewest single letter insertions, deletions and substitutions that turn one string into another.

Brute force

Trying every possible answer and keeping the best.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

These problems are about choosing and justifying an approach, so the top marks are for reasons.

• Name the strategy, then tie it to a property of the problem: overlapping sub-problems for dynamic programming, a provable local choice for greedy
• Give a counter example when asked why greedy fails: coins 1, 3 and 4 making 6, where greedy gives 4 + 1 + 1 but 3 + 3 is better
• Compare costs in numbers: 2^n subsets against an n x W table
• Say what the trade is. Dynamic programming exchanges memory for time
• For an intractable problem, say a heuristic gives a good answer, not the best, in a sensible time

Mistakes that cost marks here

amount:        0  1  2  3  4  5  6  7
fewest coins:  0  1  2  1  1  2  ?  ?