set_cover_python_greedy.py

def set_cover(universe, subsets,costs):
    cost=0
    elements = set(e for s in subsets for e in s)
    if elements != universe:
        return None
    covered = set()
    cover = []
    while covered != elements:
        subset = max(subsets, key=lambda s: len(s - covered)/costs[subsets.index(s)])
        #cover.append(subset)
        cover.append(subsets.index(subset))
        cost+=costs[subsets.index(subset)]
        covered |= subset

    return cover, cost

def main():
    #universe = set(range(1, 11))
    #universe = list(map(int, input("Universal set: ").split()))
    universe = set()
    #m = int(input("Number of subsets: "))
    m = 6
    subsets = list()
    costs = list()
    for i in range(1, m+1):
        print("S" + str(i) +" = ", end='')
        s = set(map(int, input().split()))
        subsets.append(s)
        universe |= s
        print("Cost(S"+str(i)+")=", end='')
        c = int(input())
        costs.append(c)

    cover, cost = set_cover(universe, subsets, costs)
    print("Cost =", cost)
    #print("Result =",cover)
    print("Result={", end='')
    for i in range(len(cover)):
        print("S" + str(cover[i]+1), end='')
        if (i != len(cover) - 1):
            print(end=",")
    print(end="}")

if __name__ == '__main__':
    main()