使用广度优先搜索的非递归 0/1 背包算法

Question

我遇到了一个有趣的问题，叫做背包。您有一个项目列表，所有项目都有一个值和一个重量。然后，您必须找到使求和对象的价值最大化的项目组合，并保持在一定限度内。我在某处看到这是一个搜索问题，您可以使用不同的搜索算法。现在我尝试用广度优先来实现它。

在维基百科上找到的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 队列。对于 selected 的每个项目，我有两个选择：要么我拿走这个项目，要么不拿。无论如何，具体来说：在我的上下文中，上面的伪代码我不明白的是：

当我 select 一个项目时，我是否将它两次推送到队列并将其中一个标记为已使用，一个标记为未使用？
我怎么知道当前是否是目标？我假设它类似于当没有更多节点可供探索时，这意味着我们处于叶节点。但是会有很多叶节点，那么我应该选择哪个以及如何选择？
与电流相邻是什么意思？如果我只有一个列表或一个项目数组（项目有一个 ID、一个重量和一个值），我怎么知道哪个是相邻的？

Answer 1

假设您有 4 件不同的物品。那么你正在搜索的图形是一个像这样的超立方体（图像来自Yury Chebiryak）：

节点处的二进制数是所有可能的背包，第n位为0表示第n项是不在背包中，1 表示在背包中，例如 0000 表示背包是空的，1001 表示背包中包含第一项和第四项，依此类推。

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

只有在寻找 "good enough" 解决方案而不是最佳解决方案时，目标才有意义。要确定当前节点是否是目标，您只需计算出当前背包的值并将其与目标值进行比较。

如果您想要最佳解决方案，那么广度优先搜索对您没有帮助，因为您需要探索图中的每个节点。 Dynamic programming or backtracking (which is a kind of Depth First Search) 将允许您减少搜索 space.

如果您想要 "good enough" 解决方案，那么 FIFO branch-and-bound or hill climbing（从随机背包开始）是使用 breadth-first 搜索的有效方法。

使用广度优先搜索的非递归 0/1 背包算法

Non-recursive 0/1 Knapsack algorithm using Breadth-first Search

algorithm

breadth-first-search