贪婪多重背包（最小化/减少箱子数量）

Question

其实，我对这个问题已经有了部分答案，但我在想这段简单的贪心算法代码是否可以推广成更接近最佳解决方案的东西。

我是怎么遇到这个问题的（虽然和问题本身无关，但可能有趣）：

我收到了一大堆对象（这些对象是一些堤坝的资料，每个堤坝的形状大致相同），我可以根据某个属性（堤坝的名字）把它们分组。我的程序的输出需要送到一个外部程序，而这个程序必须手动调用（别问我为什么），而且它不能从错误中恢复（只要出错一次，整个批次就会停止）。

在我使用这个程序的应用中，对分组的数量和每组的最大大小没有严格要求，我尝试做到：

保持组的数量少（尽量少调用程序）。

保持每组的大小小（如果某个批次失败，损失会更小）。

把相似的东西放在一起（如果一组出错，可能整组都会出问题）。

因为时间不多，我写了一个简单的贪心函数来把这些集合分组。

有个同事建议我可以给数据加点噪声，看看我找到的近似解决方案的周围情况，我们也在想这些找到的解决方案离最佳方案有多远。

虽然这和最初的任务无关，因为不需要一个真正的最佳解决方案，但我想把这个问题分享给大家，看看会有什么评论。

def group_to_similar_sizes(orig, max_size=None, max_factor=None):
    """group orig list in sections that to not overflow max(orig) (or given max_size).

    return list of grouped indices, plus max effective length.

    >>> group_to_similar_sizes([1, 3, 7, 13])
    ([[2, 1, 0], [3]], 13)
    >>> group_to_similar_sizes([2, 9, 9, 11, 12, 19, 19, 22, 22, ])
    ([[3, 1], [4, 2], [5], [6, 0], [7], [8]], 22)

    result is independent of original ordering
    >>> group_to_similar_sizes([9, 19, 22, 12, 19, 9, 2, 22, 11, ])
    ([[3, 1], [4, 2], [5], [6, 0], [7], [8]], 22)

    you can specify a desired max size
    >>> group_to_similar_sizes([2, 9, 9, 11, 12, 19, 19, 22, 22, ], 50)
    ([[3, 2, 1], [6, 5, 4], [8, 7, 0]], 50)

    if the desired max size is too small, it still influences the way we make groups.
    >>> group_to_similar_sizes([1, 3, 7, 13], 8)
    ([[1], [2, 0], [3]], 13)
    >>> group_to_similar_sizes([2, 9, 9, 11, 12, 19, 19, 22, 22, ], 20)
    ([[1], [3, 2], [4, 0], [5], [6], [7], [8]], 22)

    max size can be adjusted by a multiplication factor
    >>> group_to_similar_sizes([9, 19, 22, 12, 5, 9, 2, 22, 11, ], max_factor=0.75)
    ([[2], [3], [4, 1], [5, 0], [6], [7], [8]], 22)
    >>> group_to_similar_sizes([9, 19, 22, 12, 5, 9, 2, 22, 11, ], max_factor=1.5)
    ([[2, 1], [6, 5], [7, 3, 0], [8, 4]], 33)
    """

    ordered = sorted(orig)
    max_size = max_size or ordered[-1]
    if max_factor is not None:
        max_size = int(max_size * max_factor)

    orig_ordered = list(ordered)
    todo = set(range(len(orig)))
    effective_max = 0

    result = []
    ## while we still have unassigned items
    while ordered:
        ## choose the largest item
        ## make it member of a group
        ## check which we can still put in its bin

        candidate_i = len(ordered) - 1
        candidate = ordered.pop()
        if candidate_i not in todo:
            continue
        todo.remove(candidate_i)

        group = [candidate_i]
        group_size = candidate

        for j in sorted(todo, reverse=True):
            if orig_ordered[j] + group_size <= max_size:
                group.append(j)
                group_size += orig_ordered[j]
                todo.remove(j)

        result.insert(0, group)
        effective_max = max(group_size, effective_max)

    return result, effective_max

算法优化算法复杂度数据分组噪声处理贪婪算法多重背包问题近似解决方案批处理系统

贪婪多重背包（最小化/减少箱子数量）

1 个回答

撰写回答