資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用分支限界法在C/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年1月29日
2K+ 次瀏覽
廣告