python - 带权重的位掩码

Question

我有以下对:

pairs = [(1,9),(5,5),(6,4),(2,8)]

从这对元素中我只能取出一个元素。我需要生成 n 个具有最小总和的二进制掩码组合列表，其中 0 表示第一个元素，1 表示第二个元素。

如果 n == 5，则提供示例的输出:
[0,0,1,0], [0,1,1,0], [0,0,0,0], [0,1,0,0], [0,0,1, 1]

是这样的Knapsack Problem ？执行此操作的最佳算法是什么？

Answer 1

下面代码背后的想法是枚举排序的组合 递归地(好吧，不使用递归)对列表的尾部， 然后在使用较小的组合之间进行排序合并 第一对的元素以及使用较大者的组合 第一对的元素。使用最小化空间需求 生成器(通常应按元素数量的顺序排列) 你拿)。

import collections
import itertools


def extend_sorted(pair, sequence):
    argmin_pair = min(range(2), key=pair.__getitem__)
    min_pair = pair[argmin_pair]
    argmax_pair = 1 - argmin_pair
    max_pair = pair[argmax_pair]
    buffer = collections.deque()
    for sub_combo, sub_total in sequence:
        while buffer and buffer[0][1] < min_pair + sub_total:
            yield buffer.popleft()
        yield ([argmin_pair] + sub_combo, min_pair + sub_total)
        buffer.append(([argmax_pair] + sub_combo, max_pair + sub_total))
    while buffer:
        yield buffer.popleft()


def enumerate_least_sums(pairs):
    sequence = [([], 0)]
    for pair in reversed(pairs):
        sequence = extend_sorted(pair, sequence)
    for combo, total in sequence:
        yield combo


if __name__ == "__main__":
    print(*itertools.islice(enumerate_least_sums([(1, 9), (5, 5), (6, 4), (2, 8)]), 5))

输出:

[0, 0, 1, 0] [0, 1, 1, 0] [0, 0, 0, 0] [0, 1, 0, 0] [0, 0, 1, 1]