Capstone: Meridian's Day Planner
In short: this capstone chains the section together — the knapsack lesson's capacity check, the bitmask lesson's exact-tour table, and its walk-back — to score every possible set of jobs by the shortest round that visits them, and keep the best legal one. The twist is that the most profitable set on paper can be illegal (too heavy), and the best legal set can leave out the richest job, because profit depends on both what you load and how far driving it costs, and neither greedy rule alone sees both.
Every morning the planner is given the day's jobs, one van, a weight limit, and the cost of driving a kilometre. Each job sits at a stop and pays a fee, and the streets between stops are one-way. A job at a far stop might pay less than the fuel it takes to get there, and the van can't carry everything. Which jobs to take and in what order to drive them can't be decided separately. The best set depends on the round, and the round depends on the set.
This capstone puts the section together. You'll use knapsack's capacity check, the bitmask tour table and the walk-back, and then ask a question that none of the earlier lessons did: how do you know the plan you were handed is any good?
Recognising the shape
Every lesson in this section was the same idea, a table of subproblem answers filled in dependency order. The part that changed was the state. Before writing any code, name the state:
| The question sounds like… | State | Lesson |
|---|---|---|
| "choose items under a limit" | item × capacity (× a second limit) | knapsack |
| "move across a map, only forwards" | row × column (× direction, × resource) | grids |
| "a hierarchy, each part depends on its children" | node × a few flags | trees |
| "which of a small set is done, and where am I" | set × current item | bitmask |
| "best of the last k" | index, with a deque over the window | optimisation |
| "a contiguous stretch" | left end × right end | interval DP (not covered here) |
The day planner is a set problem, since there are at most eight stops and the rest of the round depends only on which are done and where the van is. It also has a limit on top, which is where the knapsack check comes in.
One table, every round
The exact-tour table from the bitmask lesson already holds more than the full
tour: dp[S][j] is the shortest route through every set S. Close each
row with the trip home and you get the shortest round for every set of stops
at once. The planner then only has to score each set:
- Skip the set if its jobs weigh more than the van carries.
profit = fees of the set − km_cost × shortest round of the set.- Keep the best, with the empty plan (stay at the depot, profit 0) as the baseline.
Here's the scoring for three jobs: the Bakery at stop 1 (4 kg, fee 30), the Florist at stop 2 (5 kg, 26) and the Garage at stop 3 (3 kg, 20). The van carries 9 kg and a kilometre costs 2. The distances are the one-way four-stop map from the bitmask lesson.
Every set the van might serve is scored once. The set table supplies each set's shortest round, the load check throws out what the van can't carry, and the best profit wins.
The empty plan takes no jobs and drives nowhere, for a profit of 0. Every other plan has to beat it. 8 cells. At index 0.
Notice the last two steps. The most profitable plan on paper is illegal, and the best legal plan leaves out the most valuable job. Neither "take the richest jobs" nor "take the closest stops" would have found it, and the next prediction shows how far even a sensible-sounding greedy rule falls short on the round alone:
dist = [[0, 2, 9, 10], [3, 0, 6, 4], [8, 7, 0, 3], [6, 4, 5, 0]]
at, left, km = 0, {1, 2, 3}, 0
while left:
nxt = min(left, key=lambda s: dist[at][s])
km += dist[at][nxt]
left.remove(nxt)
at = nxt
km += dist[at][0]
print(km)Now score the sets yourself. Each row is a set of stops (in order of size), and the columns are its load, its shortest round and its profit. Change a fee, the capacity or the cost per km, and watch the winning row move:
Your planner's own table for the day. One row per set of stops, scored from the shared tour table, and the best legal row stays marked.
How many plans is that avoiding? A plan is a set of stops plus an order for them:
import math
print(sum(math.comb(8, k) * math.factorial(k) for k in range(9)))Easy to check
Now turn it round. Someone hands you a plan, say from a colleague, a cleverer algorithm, or a driver who knows a shortcut. Is it valid, and how long is it? Answering that takes one pass over the plan: it starts and ends at the depot, no stop appears twice, the loads fit, and then you add up the km.
A checker has to be complete, though, or it proves nothing:
[0, 1, 1, 0] "visits" stop 1 twice and never reaches stop 2, yet the checker approves it at 6 km. Reject any plan that repeats a stop.
The same one-pass habit shows up in the planner's own bookkeeping. The load of every set is one addition away from a smaller set's load, if you peel off the lowest bit:
Hard to find
Finding the best plan took about 2ⁿ · n² steps. Checking one takes about n. That gap isn't a quirk of this planner. For the round-trip problem nobody knows a method that finds the best answer in time growing like a polynomial in n, and there are good reasons to believe none exists. Checking a proposed answer is still fast, though. Problems like this, where answers are hard to find and easy to check, include packing, scheduling, routing and timetabling, and they sit underneath most of logistics.
Finding the best plan costs about n² · 2ⁿ steps and checking one about n, so finding is about n · 2ⁿ times the work: 2,048 times at 8 stops, just over a million at 16, and about 21 million at 20, doubling with every stop after that. The exact planner is the right tool for a morning with 8 stops. For a depot with 60 stops a day, Meridian needs a fast heuristic that builds a good plan, plus this checker to prove every plan that goes out is valid.
That n² · 2ⁿ figure is time: every set, every ending stop, every predecessor. The shared tour table itself holds one cell per set-and-ending-stop pair, so it costs O(2ⁿ · n) space — the same table the bitmask lesson built, reused here rather than rebuilt. The checker needs none of that: one pass over the given plan is O(n) time and O(1) extra space, which is the whole reason "easy to check" is a meaningfully smaller claim than "easy to find".
What does that mean in practice?
- Small days: solve exactly. With 8 stops the table is instant, and the answer is provably the best.
- Big days: build a good plan quickly (nearest-first, then keep reversing a stretch of the round while that shortens it), and always run the checker, so that whatever goes out is at least legal.
- Anything in between: split the day into small groups of stops, solve each group exactly, and stitch them together.
❓ Cross-question: "If checking is fast, can't I find the best plan by checking every plan?" That's brute force: 109,601 plans for 8 stops, and about 10⁸² for 60. A fast check doesn't help when there are that many candidates to check. That's exactly the gap between finding and checking.
Your exercises
The ladder mirrors the planner. The warmup is the checker and the drill is the load of every set. The build returns every set's shortest round. The boss splits the stops between two vans using submask enumeration, and the capstone schedules jobs with deadlines, where a greedy order (earliest deadline first) turns the problem into a knapsack over time, so two table shapes work together.
Idioms & real-world patterns
Tuples make tie rules honest
key = (profit, -km, -mask) compares candidates exactly as the rule reads:
higher profit, then fewer km, then the smaller set. Python compares tuples
position by position, so one > implements a three-level rule with no nested
ifs.
⚡ Advanced: what real planners add
Time windows ("the bakery only accepts deliveries before 9"), several vans, driver breaks and traffic by time of day all grow the state. Exact DP stops being practical almost at once, and production routing tools combine heuristics, local search and exact solvers on small pieces. Each of those pieces is a table you now know how to build.
Quick practice
candidates = [
(18, 20, 0b0101),
(18, 14, 0b1001),
(18, 14, 0b0011),
]
best = max(candidates, key=lambda c: (c[0], -c[1], -c[2]))
print(best)The best legal plan is Bakery alone for a profit of 20, but this prints 42 because the 12 kg set is scored and kept even though the van only carries 9. Skip any set that's too heavy.
🎯 Your turn
Write plan_day(jobs, capacity, dist, km_cost). jobs[i] = [name, kg, fee] sits at
stop i + 1, stop 0 is the depot, and dist[a][b] is the km from a to b.
Choose the jobs (total kg ≤ capacity) and their round to maximise
fees − km_cost × km. Return {"profit": …, "km": …, "order": [0, …, 0]}, or
{"profit": 0, "km": 0, "order": [0]} when staying home is best.
- the three jobs above, capacity 9,
km_cost2 →{"profit": 26, "km": 12, "order": [0, 1, 3, 0]}
Ties: higher profit, then fewer km, then the smaller bitmask. Recover the order exactly as in the exact tour.
Then press ▶ Run, tap the Live App try chips, and hit ✓ Check. Green means Meridian's day planner is built. ✅