要求:設計0/1背包問題的分支限界算法,利用c語言(c++語言)實現算法,給出程序的正確運行結果。
註意:
1. 把物品按照單位體積的價值降序排列;
2. 構造優先級分支限界法的狀態空間樹,***n層,第i層每個節點的兩個分支分別代表第i個物品的取和不取;
3. 節點上需要保存的值有:S代表已裝入背包的物品的總體積,V代表已裝入背包的物品的總價值,u代表當前節點的上界,計算公式如下:
u=V+(C-S)(vi+1/si+1)
其中C是背包的總容積,vi+1代表第i+1個物品的價值,si+1代表第i+1個物品的體積。
4. 選擇適當的數據結構(如最大堆,或者基本的線性數組)實現算法,輸出最後結果。