时间戳

首页 > 解决方案 > 使用约束遍历 0、1 的列表

list - 使用约束遍历 0、1 的列表

问题描述

如果在某个地方得到了回答，我很抱歉，我尝试搜索，但我不知道这种问题是否有特定的名称，所以我的搜索中没有任何结果......

我有一个对象列表，这些对象中的每一个都可以被接受或拒绝。每个组合都分配了一个值，而某些组合无效。（例如，我们有 4 个对象，而对象 1 和 2 不在一起，那么每个接受对象 1 和 2 的组合都是无效的。）事先不知道哪些对象不在一起，它是仅通过查看对无法找到无效的。（例如，对象 1、2 可能一起有效，对象 2,3 有效，对象 1,3 有效，但 1,2,3 无效。）我将其建模为 0 和 1 的列表，所以现在我想遍历这些列表以一种有效的方式找到具有最大值的列表。

我的想法是像树一样遍历列表，从全零开始，然后在每一步中将零翻转为一，例如，对于 3 个对象，这给出了树

                000
            /    |    \
        100     010     001
        / \     / \     / \
      110 101 110 011 101 011
        \  \   \   /   /   /
                111

这实际上比仅列出所有 2^n 选项更糟糕，因为存在重复项，但是如果我发现它无效，我可以在每个节点处停止。保存无效的组合并保留所有已访问节点的列表，我可以确保我不会重新访问已检查的节点。（但如果他们已经被访问过，我仍然需要检查它们）

有没有更好的方法来做到这一点？

标签： listalgorithmmaximization

解决方案

您可以尝试构建变体树（正如您所注意到的，最多 2^n 个选项），但尽早剪掉不合适的分支。

在下面的示例中，我设置了两个二进制掩码 - 没有 1,2,3 一起，没有 2,4

def buildtree(x, maxsize, level, masks):
    if level == maxsize:
        print("{0:b}".format(x).zfill(maxsize))
    else:
        buildtree(x, maxsize, level + 1, masks)
        t = x | (1 << level)
        good = True
        for m in masks:
            if (t & m) == m:
                good = False
                break
        if good:
            buildtree(t, maxsize, level + 1, masks)

buildtree(0, 4, 0, [7, 10])

0000
1000
0100
1100
0010
0110
0001
1001
0101
1101
0011

也可以删除一些掩码，但代码会更复杂

推荐阅读