discreteoptimization / setcover Goto Github PK

In data/sc_8661_1, line 1272, the entry is 1999 -1, i.e. cost 1999 for a single-elemented set {-1}. Are negative element values valid? Or is this a flaw?

@ccoffrin greedy_001 solution (possibly others too, haven't looked into them yet) keeps adding sets until getting full coverage. However - some sets are added for which their items are already covered by previously added sets, thus adding cost but without any value gain.
By adding the following inside the main loop: (tested in 3.10, not in earlier Python versions)

        if len(set(s.items).intersection(covered)) == len(set(s.items)):
            continue

this can be avoided

Why is covered spelt as 'coverted' in the solve_it() function for the greedy folder? Took me a while to figure that out.