A round trip through every city
Some problems ask for the best order in which to do a small number of things: the order to visit a few cities, or to run a few jobs. Trying every ordering solves them up to about 10 items, because items have orderings: is about 3.6 million, and is about . This lesson reaches about 20 items with dynamic programming whose states are sets of the items. Its first problem is the best known of the kind, the travelling salesman problem.
There are cities in three-dimensional space, and city sits at the point . Travelling from a city at to a city at costs : you pay the horizontal distance, and you pay for climbing but not for descending.
Start at city 1, visit every other city at least once and return to city 1. Print the smallest total cost. The input gives , then one line per city.
Constraints
- No two cities are at the same point
Sample 1 · Input
2 0 0 0 1 2 3
Output
9
Sample 2 · Input
3 0 0 0 1 1 1 -1 -1 -1
Output
10
In the first sample the leg from city 1 up to city 2 costs and the leg back down costs , so the round trip costs 9. The two directions of a leg can cost different amounts, because only climbing is paid for. In the second sample the round trip costs .
The statement says "at least once", so a route may pass through a city it has already visited. With this cost that never saves anything, because going straight from one city to another costs no more than going by way of a third (the Deeper read at the end of this part gives the reason). So we look for the cheapest round trip that visits every city exactly once.
The samples are too small to show how the search goes, so our example has four cities. They are numbered from 0, the way the program will number them, so the starting city, which the problem calls city 1, is city 0. A driver starts there, at the depot, delivers to cities 1, 2 and 3 in some order and drives back. The example gives the cost of each leg directly, as a driving time in minutes that is the same in both directions:
cost, so that entry is cost[1][3].A round trip is fixed by the order of cities 1, 2 and 3. There are orders, few enough to list:
| Order | Legs | Total |
|---|---|---|
| 27 | ||
| 21 | ||
| 30 | ||
| 21 | ||
| 30 | ||
| 27 |
The cheapest round trip takes 21 minutes. Two orders reach it, and each is the other driven backwards. Driving to the nearest unvisited city each time does not find it: that rule gives , which takes 30 minutes, because it leaves the far city for last and then pays 12 to get home.
Six orders are quick to list, but the number grows fast. With 17 cities, the limit of the problem, the 16 cities after the first can be ordered in ways:
A loop written in Python runs roughly simple operations a second, so even at one operation per order the search would take more than three weeks.
Deeper read: why no city needs a second visit
Suppose a walk goes from a city to a city and on to a city , and is a city that the walk also visits at another time. Replace the two legs by the single leg from to , or by nothing when and are the same city. The walk still visits every city.
The direct leg also costs no more than the two legs it replaces. Each of its two horizontal distances, along and along , is at most the sum of the same distance on the two legs, by the triangle inequality for absolute values, and the same holds for its climb. With , and for the heights of the three cities:
Repeating the replacement removes every repeated visit without raising the cost, and what is left is a round trip that visits each city exactly once. In the second sample the official explanation walks through the cities 1, 2, 1, 3, 1 for a cost of 10, and the round trip also costs 10.
A state for each set and last city
The six orders in the table repeat each other's work. Compare two of them after three legs. The route has cost so far, and the route has cost . Both have visited the same cities and both are now at city 3, so whatever comes next costs the same for both. Here only the drive home is left, and on a larger map it would be a whole sequence of cities.
Any way of finishing the 18-minute route also finishes the 15-minute route, 3 minutes cheaper, so the 18-minute route cannot be the start of a cheapest round trip, and we can drop it. The frog's table kept one cheapest cost per stone by the same argument.
dp[1111][3] on the box is explained below.The set of visited cities is not enough to compare two routes. The routes and have visited the same cities, and so far they cost 8 and 7 minutes. The cheaper one is at city 1, which is 11 minutes from city 3, and the other is at city 2, which is only 7 minutes from it. A table that kept only the cheaper route would lose the better way to reach city 3. Two things about a partial route matter for what follows: the set of cities it has visited, and the city where it is now.
So a state is a pair: a set of cities that contains city 0, and a city of . Let dp[S][v] be the smallest cost of a route that starts at city 0, visits every city of exactly once and no other city, and ends at . With cities there are such sets and at most last cities for each, so there are at most states. For 17 cities that is 1,114,112 states, compared with orders.
To use a set as an index into a table, we store it as a bit mask: bit of the mask is 1 when city is in the set, with city 0 as the rightmost bit. The set of cities 0, 1 and 3 is the mask 1011, which is the number 11, and all four cities are 1111. From here on we write a set as its mask, so the two routes in the figure meet in the state dp[1111][3]. Dynamic programming whose states contain a set stored this way is called bitmask DP.
The transition from the last leg
For the transition, take a route that visits the set and ends at , and look at its last leg. The leg arrives at from some other city of . Before that leg, the route had visited the cities of except and was at , and the cheapest way to get that far costs , where is the set without city . Every city of that smaller set gives one candidate, and the transition keeps the smallest:
The base case is dp[0001][0] = 0, the route that has visited only city 0 and has not moved. No other state ends at city 0, because the route leaves city 0 at the start and returns only after the last city. An entry with no route holds infinity, which is larger than every candidate that has a route.
An evaluation order has to put each entry after the entries it depends on. Removing a city from a set changes a 1 bit of its mask to 0, which makes the number smaller. So every entry reads only entries with smaller masks, and filling the masks in increasing order computes each entry after all the entries it reads. Here is the finished table for the example, with one row for each mask that contains city 0:
The mask 0111 is the set of cities 0, 1 and 2. A route that visits them and ends at city 1 was at city 2 before its last leg, since city 0 cannot come in the middle. So dp[0111][1] is dp[0101][2] plus the leg from city 2 to city 1, which is . The entry for city 3 in the last row has two candidates, one for each highlighted entry of row 0111. City 0 would give a third, but dp[0111][0] has no route. The two candidates are the two routes in the figure:
A state stops at the last city, so the leg back to city 0 is added at the end. The answer is the smallest of dp[1111][v] + cost[v][0] over the three possible last cities:
That matches the table of orders. The smallest entry of the last row is the 15, but its route ends at city 3, which is 12 minutes from the depot.
Step through the table
The widget fills the same table one entry at a time. The entries that a step reads are dashed, and the candidate it keeps is green. The last two steps add the leg back and then follow the kept choices from the answer back to the start, the way parent links rebuilt the frog's route.
Click an entry to jump to its step, or edit a driving time to see the table change. One-way times loads a map on which the two directions of a leg take different times, as they do in the AtCoder problem.
The route table in code
The program stores the table as one row per mask, so the state is dp[mask][v]. It uses three operations on a mask:
(mask >> v) & 1shifts the mask right byvplaces and keeps the lowest bit, so it is 1 when cityvis in the set.1 << vis the mask with only bitvset, andmask ^ (1 << v)flips bitvof the mask. For a set that contains cityv, the result is the set without it.(1 << n) - 1is the number whose lowestnbits are all 1, the set of allncities.
Every state's set contains city 0, so its mask is odd. The outer loop goes through the odd masks in increasing order. It starts at 3, because mask 1 is the base case. For each mask and each last city v in it, the innermost loop is the transition: it tries every city u of prev, the set without v. The loop over v starts at 1, because no state except the base case ends at city 0.
def shortest_tour(cost):
n = len(cost)
INF = float("inf")
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0
for mask in range(3, 1 << n, 2):
for v in range(1, n):
if not (mask >> v) & 1:
continue
prev = mask ^ (1 << v)
for u in range(n):
if (prev >> u) & 1:
dp[mask][v] = min(dp[mask][v], dp[prev][u] + cost[u][v])
full = (1 << n) - 1
return min(dp[full][v] + cost[v][0] for v in range(1, n))
n = int(input())
cities = [tuple(map(int, input().split())) for _ in range(n)]
cost = [[abs(p - a) + abs(q - b) + max(0, r - c) for p, q, r in cities]
for a, b, c in cities]
print(shortest_tour(cost))On the second sample the program prints 10.
Python details
cost[u][v] is the cost from city u to city v: the comprehension takes the source in the outer loop and the target in the inner one.
Entries start at float("inf"), and infinity plus a cost is still infinity.
The table has entries, one per state, so the program needs memory. Its time is the work of all the entries added together. Each entry that is filled tries up to cities, so the program takes time. Only the odd masks are filled, and each of the 16 cities after city 0 is in half of them, so for 17 cities the innermost test runs
On the largest official sample, which has 17 cities, the program took 0.5 seconds on our laptop, and the limit is 2 seconds.
Worked example
Predict each entry yourself
Switch on Predict the next step to work out each entry before the trace shows it. Besides the four cities, the trace runs the second AtCoder sample, where both directions around the loop cost 10; the one-way times from the widget, where the best loop costs 9 and the same loop driven backwards costs 32; and a depot with no other city, for which the answer is 0.
Bit v of a mask says whether city v has been visited. Start with mask 0001: only the depot, city 0, where the route stands at cost 0.
- mask
- 0001
- states
- 8 masks × 4 cities
Change the example input
Current result: 21
Recall The driver may start at any city and does not drive back. What changes in the program?
Every city can be the start, so every set of one city is a base case: dp[1 << v][v] = 0 for each v. A set no longer has to contain city 0, so the loops run over all masks and all cities. The answer is the smallest dp[full][v], with no leg added. For the four cities of the example it is 10, for the route .
Deeper read: count the routes with the same states
The frog's table kept a minimum, and a table of the same kind with a sum in place of the minimum counted the ways to climb stairs. The route table changes in the same way. A route that visits every city of a map exactly once is called a Hamiltonian path, and this problem counts the ones that lead from the first city to the last:
There are cities and one-way flights between them. Count the routes from city 1 to city that visit every city exactly once, and print the count modulo .
The input gives and , then one line for each flight from city to city .
Constraints
Sample · Input
4 6 1 2 1 3 2 3 3 2 2 4 3 4
Output
2
In the sample two routes visit all four cities, and , so the answer is 2. We number the cities from 0 again, so a route starts at city 0 and ends at city .
The states are the ones the round trip used. Let dp[S][v] be the number of routes that start at city 0, visit exactly the cities of , each once, and end at . The last leg of such a route is a flight into from a city of , and what comes before it is one of the routes that end at . Routes with different last flights are different routes, so the candidates are added:
The sum has one term for each flight into that starts in the rest of the set. The base case is dp[0001][0] = 1, the one route that has not left yet, and the answer is dp[full][n - 1], where full is the set of all cities. No leg back is added. In the sample dp[0111][1] and dp[0111][2] are both 1, for the routes and . Both cities have a flight to city 3, so dp[1111][3] is .
The list into[v] holds the starting city of every flight into v, so the innermost loop reads only the cities that can come just before v. A flight that the input lists twice is in the list twice, so a route that uses it is counted once for each copy. The USACO Guide's solution counts it the same way.
A route that reaches city before it has visited every city cannot be completed, so the program skips every set that contains city except the full one, which halves the work.
MOD = 10**9 + 7
def count_routes(n, flights):
into = [[] for _ in range(n)]
for a, b in flights:
into[b - 1].append(a - 1)
dp = [[0] * n for _ in range(1 << n)]
dp[1][0] = 1
full = (1 << n) - 1
for mask in range(3, 1 << n, 2):
if (mask >> (n - 1)) & 1 and mask != full:
continue
for v in range(1, n):
if not (mask >> v) & 1:
continue
prev = mask ^ (1 << v)
for u in into[v]:
if (prev >> u) & 1:
dp[mask][v] += dp[prev][u]
dp[mask][v] %= MOD
return dp[full][n - 1]
n, m = map(int, input().split())
flights = [tuple(map(int, input().split())) for _ in range(m)]
print(count_routes(n, flights))On the sample the program prints 2.
For 20 cities the table has entries.
With 400 flights, the most the limits allow, the program took 2.2 seconds and 330 MB of memory on our laptop, and the limit is 1 second. The USACO Guide gives the same warning for its Python solution. At this size the problem needs the C++ version.
The set as the whole state
The route states needed the last city because the next leg starts from it. In the next problem the rest of the solution depends on the set alone, so the set is the whole state.
There are men and women. is 1 when man and woman are compatible and 0 when they are not. Count the ways to split everyone into man-woman pairs in which every pair is compatible, modulo .
The input gives , then the table , one line per man.
Constraints
- Each is 0 or 1
Sample 1 · Input
3 0 1 1 1 0 1 1 1 1
Output
3
Sample 2 · Input
1 0
Output
0
We number the men and the women from 0. In the first sample man 0 is not compatible with woman 0, and man 1 is not compatible with woman 1. Three pairings avoid both: the women given to men 0, 1 and 2 are 1, 0, 2, or 1, 2, 0, or 2, 0, 1.
A pairing gives each man a different woman, so it is an ordering of the women, and at the limit there are orderings to try.
We pair the men one at a time instead, in the order man 0, man 1, man 2 and so on. After the first men have been paired, the choices left for the other men depend only on which women are taken. Which of the first men has which of those women makes no difference to the men still waiting. The number does not need to be stored either: it is the number of women taken, which is the number of 1 bits in the mask, called its popcount.
So let dp[S] be the number of ways to pair the first men with exactly the women in , where is the number of women in . For the transition, look at the last of those men, man . He is paired with a woman of who is compatible with him, and the men before him are paired with the other women of in one of ways:
The base case is dp[000] = 1, the one way to pair nobody, and the answer is the entry for the set of all the women. Here is the table for the first sample, with woman 0 as the rightmost bit of a mask:
The entry dp[001] is 0 because its only man, man 0, is not compatible with woman 0. In dp[011] the last man is man 1. He can take woman 0, which leaves woman 1 for man 0 in dp[010] = 1 way, and he cannot take woman 1. In dp[111] the last man is man 2, who is compatible with everyone, so the entry is dp[110] + dp[101] + dp[011], which is 3.
The pairings in code
The masks are filled in increasing order, and mask.bit_count() is the popcount of a mask, so the last man paired is mask.bit_count() - 1.
MOD = 10**9 + 7
def count_matchings(compat):
n = len(compat)
dp = [0] * (1 << n)
dp[0] = 1
for mask in range(1, 1 << n):
man = mask.bit_count() - 1
for woman in range(n):
if (mask >> woman) & 1 and compat[man][woman]:
dp[mask] += dp[mask ^ (1 << woman)]
dp[mask] %= MOD
return dp[(1 << n) - 1]
n = int(input())
compat = [list(map(int, input().split())) for _ in range(n)]
print(count_matchings(compat))On the first sample the program prints 3.
At the limit there are masks and each tries up to 21 women, so the program makes about 44 million checks. That is time and memory.
With 21 men and women who are all compatible, the program took 2.1 seconds on our laptop, and the limit is 2 seconds. Submit it as PyPy, which AtCoder offers and which runs loops like these several times faster.
Deeper read: a pair of values for each set
In this problem the value stored for a set is a pair of numbers:
There are people with weights and one elevator that carries at most in a ride. Print the fewest rides that take everyone to the top.
The input gives and , then the weights.
Constraints
Sample · Input
4 10 4 8 6 1
Output
2
In the sample the weights add up to 19, which is more than the limit of 10, so one ride is not enough. Two rides are enough: 4 and 6 go in one, 8 and 1 in the other.
Think of the people boarding one at a time in some order. Each person joins the current ride if their weight still fits. Otherwise that ride leaves, and a new one starts with them.
Trying every order would find the answer. Take any division of the people into rides, and let them board in the order that lists the people of its first ride, then those of its second, and so on. That order uses no more rides than the division: the people of one ride fit together, so once one of them has to start a new ride, the rest of them fit into it, and each ride of the division adds at most one ride to the count. But 20 people have orders.
As with the routes, we keep one entry for each set of people who have boarded. Two orders that have boarded the same set can differ in two ways that matter afterwards: the number of rides they have used, including the one being filled, and the weight already in that ride.
With the same number of rides, a lighter last ride is better, because anyone who fits into the heavier one also fits into the lighter one. An order with fewer rides is better even when its last ride is heavier. Even if it sent that ride off at once and started an empty one, it would have no more rides than the other order and the lightest possible last ride, and keeping the ride open only gives later people one more place to fit.
So best[S] is a pair (rides, last): the fewest rides that can carry the people of , and the lightest last ride among the ways that use that few. Pairs are compared by rides first and by last weight second. For the transition, look at the person of who boards last. The others are carried as says, with rides and weight in the last one, and either fits into that ride or starts a new one:
Each person of gives one candidate, and best[S] is the smallest of them. The base case is best[0000] = (1, 0), one empty ride, and the answer is the number of rides in the entry for everyone.
In the sample the people are numbered 0 to 3 and weigh 4, 8, 6 and 1. For the set 0011, people 0 and 1, both candidates start a second ride, because . If person 0 boards last the pair is (2, 4), and if person 1 boards last it is (2, 8), so best[0011] is (2, 4). For the full set the smallest candidate is (2, 9). One way to reach it is for person 3, who weighs 1, to board last and join a ride that holds 8.
Comparing candidates by the number of rides alone is not enough. With the weights 1, 3, 2, 2 and 2 and a limit of 5, two rides suffice, and , but a table that replaces an entry only when a candidate has fewer rides prints 3. For a set of three people who weigh 3, 2 and 2 it keeps a last ride of 3 where a last ride of 2 was possible.
Python compares two tuples by their first entries and, when those are equal, by their second entries, which is the order the pairs need. Every entry starts at (n + 1, 0). That is larger than any real pair, since people never need more than rides.
def min_rides(weights, limit):
n = len(weights)
best = [(n + 1, 0)] * (1 << n)
best[0] = (1, 0)
for mask in range(1, 1 << n):
for p in range(n):
if not (mask >> p) & 1:
continue
rides, last = best[mask ^ (1 << p)]
if last + weights[p] <= limit:
option = (rides, last + weights[p])
else:
option = (rides + 1, weights[p])
best[mask] = min(best[mask], option)
return best[(1 << n) - 1][0]
n, x = map(int, input().split())
weights = list(map(int, input().split()))
print(min_rides(weights, x))On the sample the program prints 2.
For 20 people the table holds pairs and each is the smallest of up to 20 candidates, about 21 million in all: time and memory.
With 20 people the program took 1.6 seconds on our laptop, and the limit is 1 second. Submit it as PyPy3, which CSES offers.
Transitions that remove a whole group
Each transition so far removed one item from a set. In the last problem a solution is made of whole groups, and the transition removes a group at a time.
There are rabbits, and every pair of rabbits has a score , which may be negative. Split the rabbits into groups, each rabbit in exactly one group. Every pair placed in the same group earns its score. Print the largest possible total.
The input gives , then the table , which is symmetric with zeros on the diagonal.
Constraints
- and
Sample 1 · Input
3 0 10 20 10 0 -100 20 -100 0
Output
20
Sample 2 · Input
4 0 1000000000 1000000000 1000000000 1000000000 0 1000000000 1000000000 1000000000 1000000000 0 -1 1000000000 1000000000 -1 0
Output
4999999999
In the first sample the best division puts rabbits 1 and 3 in one group, which earns 20, and leaves rabbit 2 alone. All three in one group would earn , and three groups of one would earn 0.
Number the rabbits from 0. For a set of rabbits, let score[G] be what earns as one group, the sum of over the pairs of rabbits in . Let dp[S] be the largest total for dividing exactly the rabbits of into groups. Any division of contains some group , a nonempty subset of , and its other groups divide the remaining rabbits, , for which the best total is . Trying every possible gives the transition:
Here are both tables for the first sample, with rabbit 0 as the rightmost bit of a mask:
111 a best candidate is the group 101, our rabbits 0 and 2, which are rabbits 1 and 3 of the statement. It earns 20 and leaves dp[010] = 0 for the rabbit that remains.In terms of masks, is a submask of : a mask whose set bits are all set in as well. The program has to go through every submask of a mask, and a short loop does it. The loop starts at sub = mask and moves on with sub = (sub - 1) & mask. Subtracting 1 changes the lowest set bit of sub to 0 and the zeros below it to 1s, and the AND with mask clears the 1s that are not in the mask. The result is the largest submask that is smaller than sub. From 1011 the loop visits
and then reaches 0, where it stops. The step from 1000, for example, computes 0111 & 1011, which is 0011.
The grouping in code
The first loop computes score for every mask by adding the score of each pair inside it. The second loop is the transition. It starts dp[mask] with the whole mask as one group and then tries every smaller nonempty submask as the group sub. The rest of the mask is mask ^ sub, because XOR changes the bits of sub to 0.
def best_grouping(a):
n = len(a)
score = [0] * (1 << n)
for mask in range(1 << n):
for i in range(n):
for j in range(i + 1, n):
if (mask >> i) & 1 and (mask >> j) & 1:
score[mask] += a[i][j]
dp = [0] * (1 << n)
for mask in range(1, 1 << n):
dp[mask] = score[mask]
sub = (mask - 1) & mask
while sub > 0:
dp[mask] = max(dp[mask], score[sub] + dp[mask ^ sub])
sub = (sub - 1) & mask
return dp[(1 << n) - 1]
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
print(best_grouping(a))On the first sample the program prints 20.
Each of the masks has up to submasks, but the second loop takes far fewer than steps. It runs once for each pair of a mask and one of its submasks, and there are exactly such pairs, because each rabbit is in one of three places: outside the mask, in the mask but not in the submask, or in both. For 16 rabbits that is
pairs, where is about 4.3 billion. The first loop adds checks, one for each mask and each of the 120 pairs of rabbits.
The Python program needs PyPy here as well: on the largest official sample, which has 16 rabbits, it took 2.5 seconds on our laptop, and the limit is 2 seconds.
Recall Suppose the problem asked how many ways there are to divide the rabbits into groups. Does the same transition, with a sum, count them?
No. The transition removes one group and then divides the rest, so it builds a division one group at a time, and a division with groups is built once for each of the orders of its groups. Meeting a division several times does not change a maximum, but it does change a sum: for three rabbits the sum gives 13, where there are 5 divisions.
To count each division once, let be only the group that contains the lowest-numbered rabbit of . Every division has exactly one such group, so it is built in exactly one way. The same restriction roughly halves the work of the maximum.
Time and space of these tables
- Trying every order
- A round trip from a fixed start is one of orders, which is for 17 cities.
- A set and a last city
- The round trip and Hamiltonian Flights have entries with up to candidates each. Memory is .
- The set alone
- Matching and Elevator Rides have entries with up to candidates each. Memory is .
- Submask transitions
- Grouping has one candidate for each pair of a mask and a submask, plus steps for the scores. Memory is .
Every one of these tables has at least entries, and that number doubles with each added item: about a thousand sets for 10 items, a million for 20 and a billion for 30. A limit of about 20 on the things to be ordered, paired or packed, or of about 16 when the transition removes groups, is a hint that the intended states are sets: and are both a few times .
Common mistakes
Leaving out the leg back to city 0.
- Where it breaks
- On the four-city example the smallest entry of the last row is
dp[1111][3] = 15, for the route , which ends 12 minutes from the depot. A program that returns it prints 15 where the answer is 21. - The fix
- Return the smallest
dp[full][v] + cost[v][0]. Leave the last leg out only when the problem asks for a route that does not return, as Hamiltonian Flights does.
Keeping one value for each set in the round trip.
- Where it breaks
- Suppose the table stores, for each set, only its cheapest route and the city where that route ends. For cities 0, 1 and 2 it keeps , which costs 7, and forgets , which costs 8. The leg to city 3 costs 11 from city 1 and 7 from city 2, so the forgotten route was the better start. The table reaches city 3 for 18 where 15 is possible, and the program prints 30 where the answer is 21.
- The fix
- Make the last city part of the state,
dp[S][v], so that routes that end at different cities are never compared.
Writing the submask loop without a stop at 0.
- Where it breaks
- From
sub = 0the step computes(0 - 1) & mask. The number has every bit set, so the result ismaskagain, and a loop that does not test for 0 goes around the submasks of1011forever. - The fix
- Stop when
subreaches 0, and handle the empty submask separately if the problem needs it.
Using
1 << nas the set of all cities.- Where it breaks
- With 4 cities
1 << 4is 16, which is10000in binary: a set that holds only a fifth city. The table has the rows 0 to 15, sodp[1 << 4]is outside it. Python raisesIndexError, and C++ reads memory past the end of the table. - The fix
- The set of all
ncities is(1 << n) - 1, which is1111for 4 cities.
Further reading
- USACO Guide, GoldBitmask DP(opens in a new tab)
Built around Hamiltonian Flights, then uses submask transitions to split a graph into groups, as Grouping does, and applies masks to sets of prime factors.
- Antti Laaksonen (PDF)Competitive Programmer’s Handbook, Chapter 10: Bit manipulation(opens in a new tab)
Section 10.5, pages 102 to 106, buys products over several days with a set and a day as the state, solves the elevator problem with the same pair of rides and last weight, and then sums values over all subsets.
- cp-algorithmsEnumerating submasks of a bitmask(opens in a new tab)
The
(sub - 1) & maskloop from Grouping, with the proof that going through every submask of every mask takes steps. - WikipediaHeld-Karp algorithm(opens in a new tab)
The route table under its usual name, with pseudocode and the analysis of time and space.
- Jeff Erickson (PDF)Algorithms, Chapter 3: Dynamic programming(opens in a new tab)
Section 3.4 sets out the steps from a recurrence to a table: name the subproblems, find which ones each depends on, fill them in an order that puts each after those, and add up the work. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- USACO Guide, PlatinumSum over Subsets DP(opens in a new tab)
The next step after submask loops: summing a value over every subset of every mask in instead of .
- OI Wiki, in Chinese状压 DP (Bitmask DP)(opens in a new tab)
Two examples: placing kings on a board row by row with one mask per row, which this lesson does not cover, and splitting people into groups to cross a bridge, close to Grouping.
