背包回溯

我需要使用回溯来解决背包问题。这是我可能不得不为我的问题做的一个例子。我的问题是，我怎么知道边界？我知道根节点的边界是$ 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

来源

2016-11-16 yeny314

请提供您所说的所有物品和重量限制。图为总价值40美元+30美元+50美元+10美元= 130美元的4件商品。这显然不是你提到的115美元。 –

我已经想通了：

势必=利润+ P1 + P2 +（ C - 7）* p3/w3 = $ 0 + $ 40 + $ 30 +（16 -7）X $ 50/10 = $ 115

来源

2016-11-16 18:39:42 yeny314

回答

相关问题