集合覆蓋

Vibe Prompt

「幫我用貪婪演算法解決集合覆蓋問題：有 10 個城市與 5 個廣播站，每個廣播站涵蓋不同城市。找出最小廣播站集合。」

def set_cover(universe, subsets):
    """
    universe: 所有元素的集合
    subsets: {name: set_of_elements}
    """
    remaining = universe.copy()
    selected = []
    
    while remaining:
        best_name = None
        best_covered = 0
        for name, elements in subsets.items():
            if name not in selected:
                covered = len(remaining & elements)
                if covered > best_covered:
                    best_covered = covered
                    best_name = name
        if best_name:
            selected.append(best_name)
            remaining -= subsets[best_name]
        else:
            break
    return selected

universe = set(range(10))
subsets = {
    "站A": {0,1,2,3},
    "站B": {3,4,5},
    "站C": {5,6,7},
    "站D": {7,8,9},
    "站E": {0,4,9},
}

result = set_cover(universe, subsets)
print(f"選取廣播站: {result}")

# 貪婪不保證最佳但實務上夠用
print(f"涵蓋率: {len(set.union(*[subsets[r] for r in result]))}/{len(universe)}")