使用分支限界法在C/C++中實現0/1背包問題

這個想法是為了實現貪婪方法為分數背包問題提供最佳解決方案這一事實。

為了檢查特定節點是否可以為我們提供更好的解決方案，我們計算最佳解決方案（透過節點）實作貪心方法。如果貪心法本身計算出的解比目前為止最好的解要多，那麼我們就無法透過節點獲得更好的解。

完整的演算法如下 -

• 根據每單位重量的價值比率的降序對所有項目進行排序，以便可以使用貪心法計算上限。

• 初始化最大利潤，例如 maxProfit = 0

• 建立一個空隊列 Q。

• 決策虛擬節點建立樹並將其插入或排隊到 Q。虛擬節點的利潤和權重為 0。

• 當 Q 不空或為空時執行下列操作。

  • 建立了 Q 中的項目。設提取項為u。

  • 計算下一級節點的利潤。如果利潤高於maxProfit，則修改maxProfit。

  • 計算下一級節點的界限。如果bound高於maxProfit，則將下一級節點加入Q。

  • 考慮下一級節點不被視為或考慮為解決方案的一部分的情況，並將節點添加到隊列的層級為下一級，但權重和利潤不處理或考慮下一級節點。

下面給出的插圖 -

// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10

輸出

The maximum possible profit = 235

以上是使用分支限界法在C/C++中實現0/1背包問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！