151
The set-covering problem
To recap:
•
Sets are like lists, except sets can’t have duplicates.
• You can do some interesting operations on sets,
like union,
intersection, and difference.
Back to the code
Let’s get back to the original example.
This is a set intersection:
covered = states_needed & states_for_station
covered
is a set
of states that were in both
states_needed
and
states_for_station
. So
covered
is the set of uncovered states
that this station covers! Next you
check whether this station
covers more states than the current
best_station
:
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
If so,
this station is the new
best_station
. Finally, after the
for
loop is over,
you add
best_station
to the final list of stations:
final_stations.add(best_station)
You also need to update
states_needed
.
Because this station covers
some states, those states aren’t needed anymore:
states_needed -= states_covered
And you loop until
states_needed
is empty. Here’s
the full code for
the loop:
while states_needed:
best_station = None
states_covered = set()
for station, states in stations.items():
covered = states_needed & states
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
states_needed -= states_covered
final_stations.add(best_station)
