r"""
    Greedy algorithm for various covering problems.
    approximation gaurentees depending on specifications  like set_weights and item values

    Set Cover: log(len(items) + 1) approximation algorithm
    Weighted Maximum Cover: 1 - 1/e == .632 approximation algorithm
    Generalized maximum coverage is not implemented

    References:
        https://en.wikipedia.org/wiki/Maximum_coverage_problem

    Example:
        >>> # DISABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> candidate_sets_dict = {
        >>>     'a': [1, 2, 3, 8, 9, 0],
        >>>     'b': [1, 2, 3, 4, 5],
        >>>     'c': [4, 5, 7],
        >>>     'd': [5, 6, 7],
        >>>     'e': [6, 7, 8, 9, 0],
        >>> }
        >>> max_weight = None
        >>> items = None
        >>> set_weights = None
        >>> item_values = None
        >>> greedy_soln = ut.sort_dict(ut.setcover_greedy(candidate_sets_dict))
        >>> exact_soln = ut.sort_dict(ut.setcover_ilp(candidate_sets_dict))
        >>> print('greedy_soln = %r' % (greedy_soln,))
        >>> print('exact_soln = %r' % (exact_soln,))

def setcover_greedy(candidate_sets_dict, items=None, set_weights=None, item_values=None, max_weight=None):
    r"""
    Greedy algorithm for various covering problems.
    approximation gaurentees depending on specifications  like set_weights and item values

    Set Cover: log(len(items) + 1) approximation algorithm
    Weighted Maximum Cover: 1 - 1/e == .632 approximation algorithm
    Generalized maximum coverage is not implemented

    References:
        https://en.wikipedia.org/wiki/Maximum_coverage_problem

    Example:
        >>> # DISABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> candidate_sets_dict = {
        >>>     'a': [1, 2, 3, 8, 9, 0],
        >>>     'b': [1, 2, 3, 4, 5],
        >>>     'c': [4, 5, 7],
        >>>     'd': [5, 6, 7],
        >>>     'e': [6, 7, 8, 9, 0],
        >>> }
        >>> max_weight = None
        >>> items = None
        >>> set_weights = None
        >>> item_values = None
        >>> greedy_soln = ut.sort_dict(ut.setcover_greedy(candidate_sets_dict))
        >>> exact_soln = ut.sort_dict(ut.setcover_ilp(candidate_sets_dict))
        >>> print('greedy_soln = %r' % (greedy_soln,))
        >>> print('exact_soln = %r' % (exact_soln,))
    """
    import utool as ut
    solution_cover = {}
    # If candset_weights or item_values not given use the length as defaults
    if items is None:
        items = ut.flatten(candidate_sets_dict.values())
    if set_weights is None:
        get_weight = len
    else:
        def get_weight(solution_cover):
            sum([set_weights[key] for key in solution_cover.keys()])
    if item_values is None:
        get_value = len
    else:
        def get_value(vals):
            sum([item_values[v] for v in vals])
    if max_weight is None:
        max_weight = get_weight(candidate_sets_dict)
    avail_covers = {key: set(val) for key, val in candidate_sets_dict.items()}
    # While we still need covers
    while get_weight(solution_cover) < max_weight and len(avail_covers) > 0:
        # Find candiate set with the most uncovered items
        avail_covers.values()
        uncovered_values = list(map(get_value, avail_covers.values()))
        chosen_idx = ut.argmax(uncovered_values)
        if uncovered_values[chosen_idx] <= 0:
            # needlessly adding value-less items
            break
        chosen_key = list(avail_covers.keys())[chosen_idx]
        # Add values in this key to the cover
        chosen_set = avail_covers[chosen_key]
        solution_cover[chosen_key] = candidate_sets_dict[chosen_key]
        # Remove chosen set from available options and covered items
        # from remaining available sets
        del avail_covers[chosen_key]
        for vals in avail_covers.values():
            vals.difference_update(chosen_set)
    return solution_cover