❶ 解電路板排列問題用分支限界法的時間復雜度是多少
利用優先順序分支限界法設計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.選擇適當的數據結構（如最大堆，或者基本的線性數組）實現演算法，輸出最後結果。