这是我第一次学习数据结构和算法，我卡在了Grokking算法第八章贪婪算法中，那里有一个简单的集合覆盖问题给读者。
有没有一个更简单的源代码示例，我可以参考它来理解这个示例背后的概念？
有人能解释一下集合交集是如何用简单的英语帮助得到{k4，k5}的最终结果的吗？states_needed数组是如何传递给一个散列并转换为一个集合的？
states_needed = set(["a", "b", "c", "d", "e", "f", "g", "h"])
stations = {}
stations["k1"] = set(["a", "b", "c"])
stations["k2"] = set(["c", "d", "e"])
stations["k3"] = set(["f", "g", "h"])
stations["k4"] = set(["a", "b", "c", "d"])
stations["k5"] = set(["e", "f", "g", "h"])
final_stations = set()
while states_needed:
best_station = None
states_not_covered = set()
for station, states_for_station in stations.items():
covered = states_needed & states_for_station
if len(covered) > len(states_not_covered):
best_station = station
states_not_covered = covered
states_needed -= states_not_covered
final_stations.add(best_station)
print(final_stations)字符串
1条答案
按热度按时间i7uaboj41#
*初始化数据：
states_needed：一组需要覆盖的州。stations：一个字典，其中每个键是一个站名，对应的值是该站覆盖的一组状态。*贪婪算法实现：
final_stations：最终将包含最终选择的桩号的集合。while循环就运行。*查找最佳电台：
best_station：暂时保留在目前版序中找到的最佳桩号。states_not_covered：用于跟踪best_station所覆盖的状态的集合。for循环在每个工作站上迭代，并计算此工作站将覆盖的未覆盖状态（covered）的集合。covered和states_not_covered的长度），则该站点成为新的best_station，并且states_not_covered被更新。*更新州和终点站：
states_needed以删除现在覆盖的状态。best_station将添加到final_stations。*输出：
states_needed变为空），则循环退出。final_stations集合包含以最少数量的站（根据贪婪方法）共同覆盖所有所需状态的站名称。*打印结果：
final_stations，这是算法选择的一组站点。