揹包回溯

我需要使用回溯來解決揹包問題。這是我可能不得不爲我的問題做的一個例子。我的問題是，我怎麼知道邊界？我知道根節點的邊界是$ 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

回答

相關問題