一．實驗目的
1.熟悉分支限界法的基本原理。
2.通過本次實驗加深對分支限界法的理解。
二．實驗內容及要求
內容：.給定n種物品和乙個揹包。物品i的重量是w，其價值為v，揹包容量為c。問應該如何選擇裝入揹包的物品，使得裝入揹包中物品的總價值最大?
要求：使用優先佇列式分支限界法演算法程式設計，求解0-1揹包問題
三．程式列表
#include
#include
usingnamespace std;
#definen 100
classheapnode//定義heapnode結點類
double maxbound(int i);
double knap();
void addlivenode(double up, double cp, double cw, bool ch, int level);/up是價值上界，cp是相應的價值，cw是該結點所相應的重量，ch是ture or false
stack high; /最大隊high
double w[n], p[n]; 把物品重量和價值定義為雙精度浮點數
double cw, cp, c; /cw為當前重量，cp為當前價值，定義揹包容量為c
int n; 貨物數量為
int main()
double maxbound(intk) /maxbound函式求最大上界
if (k<= n)
b +=p[k] /w[k] *cleft; 裝填剩餘容量裝滿揹包
return b;
void addlivenode(doubleup, doublecp, doublecw, boolch, intlev) 將乙個新的活結點插入到子集數和最大堆high中
//呼叫stack標頭檔案的push函式 }
double knap() 優先佇列分支限界法，返回最大價值，bestx返回最優解
up = maxbound(i + 1);
if (up >=bestp) 右子數可能含最優解
addlivenode(up, cp, cw, false, i + 1);
if (
return bestp;
heapnode node = 取下一擴充套件結點
cw =
cp =
up =
i =}四．實驗結果
分支限界法
package import import import 分支界限法解0 1揹包問題。public class bbknapsack 裝填剩餘容量裝滿揹包 if i n return b 新增新的活節點到子集樹和優先佇列中 private void addlivenode double upperp...
實驗四分支限界法實現單源最短路徑
09電信實驗班 i09660118 徐振飛 1 實驗名稱 實現書本p194頁所描述的單源最短路徑問題 2 實驗目的 1 掌握並運用分支限界法基本思想 2 運用分支限界法實現單源最短路徑問題 3 區分分支限界演算法與回溯演算法的區別，加深對分支限界法理解 3 實驗內容和原理 1 實驗原理 解單源最短路...
實驗4因果圖法
提交方式 以 學號姓名 命名的word文件。有乙個處理單價為1元5角錢的盒裝飲料的自動售貨機軟體。若投入1元5角硬幣，按下 可樂 雪碧 或 紅茶 按鈕，相應的飲料就送出來。若投入的是兩元硬幣，在送出飲料的同時退還5角硬幣。要求 用因果圖法 列出原因和結果,畫出因果圖，制定決策表 來設計測試用例。原因...