資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中使用分支定界求解 0/1 揹包問題
我們透過貪婪演算法來實現這個思想，為分數揹包問題提供最佳解決方案。
為了檢查特定節點是否能為我們提供更好的解決方案，我們採用貪婪演算法計算最優解（透過該節點）。如果貪婪演算法本身計算出的解大於到目前為止的最佳解，則我們無法透過該節點得到更好的解。
以下給出完整演算法 −
按單位重量的價值比降序對所有物品進行排序，以便可以透過貪婪演算法計算上界。
初始化最大利潤，如 maxProfit = 0
建立一個空佇列 Q。
建立一個決策樹的虛擬節點並將它插入或放入 Q 中。虛擬節點的利潤和重量為 0。
在 Q 不為空的情況下，執行以下操作。
從 Q 中建立一個物品。設抽取的物品為 u。
計算下一級節點的利潤。如果利潤高於 maxProfit，則修改 maxProfit。
計算下一級節點的上界。如果上界高於 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
更新於： 2020-01-30
1K+瀏覽
廣告