背包的回溯

Question

我需要使用回溯来解决背包问题。这是我可能不得不为我的问题所做的一个例子。我的问题是，我如何知道界限？我知道根节点的界限是$115，因为它是所有值的总和。但我不明白的是，根的右边的孩子怎么会有82美元的界限。

我发现这篇文章解释了它的意思，但我仍然感到困惑：

For a maximization problem the bound is an upper bound, 
    – the largest possible solution that can be achieved by 
      expanding the node is less or equal to the upper bound 

​

​

Answer 1

我已经弄明白了：

bound =利润+ p1 + p2 + (C -7) * p3 / w3 = $0 + $40 + $30 + (16 -7)X $50/10 = $115