Answers Built From Smaller Answers
When You Do Not Need the Table
Last timeWorking Bottom Up Instead
Some problems are solved by taking the best looking step each time, with no table and no recursion, and the difficulty is that the ones that are not look exactly the same.
The method with no machinery at all
Everything in this course has been machinery. A tree of calls, a pile of
waiting frames, a store of answers, a table filled in order. Some problems
need none of it.
Suppose a room can hold one talk at a time and a list of talks is given, each
with a start and a finish, and the aim is to fit in as many as possible. There
is a method: repeatedly take the talk that finishes earliest among those that
still fit, and never reconsider. That is it. One sort, one pass, nothing held.
And it is not an approximation. It gives the largest possible number of talks,
always, and the proof fits in a paragraph.
def most_talks(talks):
out, end = [], 0
for s, f in sorted(talks, key=lambda t: t[1]): # earliest finish first
if s >= end:
out.append((s, f)); end = f
return out
print(most_talks([(0, 6), (1, 4), (5, 7), (3, 8), (8, 9)]))
def pack_by_value(items, cap):
out, left = [], cap
for w, v in sorted(items, key=lambda i: -i[1] / i[0]): # best value per kilo
if w <= left:
out.append((w, v)); left -= w
return sum(v for _, v in out)
print(pack_by_value([(10, 60), (20, 100), (30, 120)], 50)) # 220
print("the best packing of that bag is 220, so this one happens to be right")
print(pack_by_value([(3, 10), (4, 11), (5, 12)], 7)) # 21
print("the best packing of that bag is 23, taking the second and third")The check that settles it
The test is the exchange argument, and it has a fixed form worth memorising,
because it is the same argument that appeared on the network course and it
applies unchanged here.
Take any best possible answer that does not make the choice your method would
make first. Show that it can be modified to include that choice without
becoming worse. If that always works, the first choice is safe, and the same
reasoning applies to the second choice, and the whole method is correct.
For the talks: suppose a best schedule does not start with the earliest
finishing talk. Swap its first talk for the earliest finishing one. That talk
finishes no later, so everything that followed still fits, and the count is
unchanged. The modified schedule is still best and now starts with the
earliest finish. So taking it is safe.
- any best possible answer
- the choice the method would make first
- a best answer that has been modified to include that choice
Try the same argument on the bag. Suppose the best packing does not include
the item with the best value per kilo. Swap it in. But it may be heavier than
what it replaces, so something else has to come out, and what comes out might
be worth more than the gain. The exchange gets stuck, and the place it got
stuck describes the counterexample: a dense light item that blocks two items
that together are worth more. The three item bag in the code above is exactly
that.
The lesson stops here
3 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents