算法設計與分析分支限界—0-1背包問題信息工程大學國家級實驗教學示范中心計算機學科組規劃教材算法設計與分析Python案例詳解微課視頻版

解空間：{(0,0,0),(0,0,1),…,(1,1,1)}解空間樹：BAHIJKLMNODEFGC11111110000000算法設計：結點的價值上界up：得到當前結點可能得到的最大價值先進先出隊列：按照入隊的順序進行活結點的擴展約束條件：已裝包物品重量和<=c,即cw<=c，用于判斷結點是否能產生可行解限界條件：up>bestp，用于決定是否能得到最優解剪枝：對于非可行解和非最優解一律剪枝擴展結點活結點隊列最優解bestpbestx00,0,0已知條件：n=3,C=30v=(40,27,24)w=(20,15,15)樹中結點的信息：結點深度，已裝入背包價值，已占用背包容量，價值上限(x1,x2,x3)A填空題：對于n=3,背包容量C=30，物品價值v=(40,27,24)，物品重量w=(20,15,15)的實例而言，初始時，價值上界up值為（）測試擴展結點活結點隊列最優解A10HI0,0,0,58(?,?,?)B11,40,20,58(1,?,?)C01,0,0,51(0,?,?)D1死結點0E2,40,20,56(1,0,?)F12,27,15,51(0,1,?)G02,0,0,24(0,0,?)bestpbestx00,0,0ABBCCBCDEECEFGF已知條件：n=3,C=30v=(40,27,24)w=(20,15,15)樹中結點的信息：結點深度，已裝入背包價值，已占用背包容量，價值上限(x1,x2,x3)1J死結點0K3,40,20,40(1,0,0)1L3,51,30,51(0,1,1)0M3,27,15,27(0,1,0)bestpbestx401,0,0CEFGFEFJKFLMA10HI01NOB11,40,20,58(1,?,?)C01,0,0,51(0,?,?)D1死結點0E2,40,20,56(1,0,?)F12,27,15,51(0,1,?)剪枝G02,0,0,24(0,0,?)擴展結點活結點隊列最優解已知條件：n=3,C=30v=(40,27,24)w=(20,15,15)樹中結點的信息：結點深度，已裝入背包價值，已占用背包容量，價值上限(x1,x2,x3)00,0,0510,1,1GG輸入：c,n,w[],p[]輸出：bestp,bestx[]1Knapsack(c,n,w,v){2計算所有物品的總重量W和總價值V;3if(W<=c){4bestp=V;5bestx[1..n]=1;//物品全部裝包6

return;7}8將物品按單位價值非增排序;計算初始up;9創建隊列并初始化;10bestp=0;bestx[1.n]=0;11創建并初始化第一個結點N；12

//N入隊;出隊N;//這兩個操作可省略13

while(N存在){

//N不會是葉子結點14//擴展左兒子,即考慮下一物品裝包15

inti,cp,cw,up;i=N.l+1;16cw=N.cw+w[i];17if(cw<=c){//左兒子為可行結點18

cp=N.cp+v[i];up=N.up;19if(cp>bestp){//發現新的最優解20

bestp=cp;bestx[1..n]=N.x[1..n];21bestx[i]=1;}//物品i+1裝包22if(i<n&&up>bestp){//剪枝判斷23構造左兒子結點并插入隊列;}24}25//擴展右兒子結點,右兒子總是可行的26重新計算右兒子的up;27if(i<n&&up>bestp{//剪枝判斷28構造右兒子結點并插入隊列;}29//當前結點N擴展完畢30釋放N;從隊列中取下一擴展結點N;31}//while32output(bestp,bestx);33}隊列式分支限界：

按照活結點先進先出的策略進行搜索，每一個擴展結點具有相同的優