當前位置:編程學習大全網 - 網站源碼 - 分別用隊列和優先級隊列分支限界法解0—1背包問題

分別用隊列和優先級隊列分支限界法解0—1背包問題

利用優先級分支限界法設計0/1背包問題的算法,掌握分支限界法的基本思想和算法設計的基本步驟,註意其中結點優先級的確定方法,要有利於找到最優解的啟發信息。

要求:設計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. 選擇適當的數據結構(如最大堆,或者基本的線性數組)實現算法,輸出最後結果。

  • 上一篇:誰能教我用金山遊俠或者FPE修改遊戲啊!
  • 下一篇:A10cuda驅動程序要求
  • copyright 2024編程學習大全網