基于宽度优先搜索的非递归0/1背包算法

Question

我遇到了一个有趣的问题叫做背包。您有一个项目列表，它们都有一个值和一个权重。然后，您必须找到项目的组合，以最大化的对象的价值之和，并保持在一定的限度内。我在某个地方看到，这是一个搜索问题，你可以使用不同的搜索算法。现在我正试着以广度第一的方式来实现它。

在wikipedia上找到的BFS伪算法如下：

Breadth-First-Search(Graph, root):

create empty set S
create empty queue Q      

root.parent = NIL
Q.enqueue(root)                      

while Q is not empty:
    current = Q.dequeue()
    if current is the goal
        return current
    for each node n that is adjacent to current:
        if n is not in S:
            add n to S
            n.parent = current
            Q.enqueue(n)

我真的试着去理解如何把这个应用到背包问题上。

据我所知，这是关于建一棵树。我需要一次扩展和探索一个层次的每个节点。对于BFS，我需要一个FIFO队列。对于所选的每一项，我有两个选择:要么我接受该项目，要么不接受。总之，具体而言:在我的上下文中，对于上面的伪代码，我不理解的是：

• 当我选择一个项目时，我是否将它两次推到队列中，并将其中一个标记为已使用，另一个标记为不使用？
• 我怎么知道现在的目标是什么？我想这就像是当没有更多的节点需要探索的时候，这意味着我们在一个叶节点上。但是会有很多叶节点，那么我应该选择哪一个，如何选择呢？
• 与电流相邻意味着什么？如果我只有一个列表，或者一个项目数组(条目有一个ID、一个权重和一个值)，我如何知道哪个是相邻的？

Answer 1

假设你有4个不同的项目。然后，您正在搜索的图是这样一个超立方体(尤里·契伯亚克的图像)：

​

​

节点上的二进制数都是所有可能的背包，n_th位置中的0表示条目_n不在背包中，1表示它在背包中，例如0000表示空背包，1001表示包含第一项和第四项的背包，依此类推。

在每一步中，从队列中移除当前节点，如果不是目标，则通过查找与当前逐项不同的、尚未访问的所有背包来构造相邻节点。例如，如果当前节点为1001，则需要构造节点0001、1101、1011和1000。然后将这些节点添加到队列中。

目标只有在你寻找“足够好”的解决方案，而不是最好的解决方案时才有意义。要确定当前节点是否是目标，只需计算当前背包的值，并将其与目标值进行比较。

如果您想要最好的解决方案，那么广度优先搜索对您没有帮助，因为您需要探索图中的每个节点。动态规划或回溯 (这是一种深度优先搜索)将允许您减少搜索空间。

如果您想要一个“足够好”的解决方案，则FIFO 分叉装订或爬山 (从随机背包开始)是使用广度优先搜索的有效方法。