算法設(shè)計與分析 課件 8.3-分支限界 - 典型應(yīng)用 - 0-1背包問題

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

解空間：{(0,0,0),(0,0,1),…,(1,1,1)}解空間樹：BAHIJKLMNODEFGC11111110000000算法設(shè)計：結(jié)點的價值上界up：得到當前結(jié)點可能得到的最大價值先進先出隊列：按照入隊的順序進行活結(jié)點的擴展約束條件：已裝包物品重量和<=c,即cw<=c，用于判斷結(jié)點是否能產(chǎn)生可行解限界條件：up>bestp，用于決定是否能得到最優(yōu)解剪枝：對于非可行解和非最優(yōu)解一律剪枝擴展結(jié)點活結(jié)點隊列最優(yōu)解bestpbestx00,0,0已知條件：n=3,C=30v=(40,27,24)w=(20,15,15)樹中結(jié)點的信息：結(jié)點深度，已裝入背包價值，已占用背包容量，價值上限(x1,x2,x3)A填空題：對于n=3,背包容量C=30，物品價值v=(40,27,24)，物品重量w=(20,15,15)的實例而言，初始時，價值上界up值為（）測試擴展結(jié)點活結(jié)點隊列最優(yōu)解A10HI0,0,0,58(?,?,?)B11,40,20,58(1,?,?)C01,0,0,51(0,?,?)D1死結(jié)點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)樹中結(jié)點的信息：結(jié)點深度，已裝入背包價值，已占用背包容量，價值上限(x1,x2,x3)1J死結(jié)點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死結(jié)點0E2,40,20,56(1,0,?)F12,27,15,51(0,1,?)剪枝G02,0,0,24(0,0,?)擴展結(jié)點活結(jié)點隊列最優(yōu)解已知條件：n=3,C=30v=(40,27,24)w=(20,15,15)樹中結(jié)點的信息：結(jié)點深度，已裝入背包價值，已占用背包容量，價值上限(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創(chuàng)建隊列并初始化;10bestp=0;bestx[1.n]=0;11創(chuàng)建并初始化第一個結(jié)點N；12

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

while(N存在){

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

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

cp=N.cp+v[i];up=N.up;19if(cp>bestp){//發(fā)現(xiàn)新的最優(yōu)解20

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

按照活結(jié)點先進先出的策略進行搜索，每一個擴展結(jié)點具有相同的優(yōu)