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

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

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

return;7}8將物品按單位價(jià)值非增排序;計(jì)算初始up;9創(chuàng)建隊(duì)列并初始化;10bestp=0;bestx[1.n]=0;11創(chuàng)建并初始化第一個(gè)結(jié)點(diǎn)N；12

//N入隊(duì);出隊(duì)N;//這兩個(gè)操作可省略13

while(N存在){

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

inti,cp,cw,up;i=N.l+1;16cw=N.cw+w[i];17if(cw<=c){//左兒子為可行結(jié)點(diǎn)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é)點(diǎn)并插入隊(duì)列;}24}25//擴(kuò)展右兒子結(jié)點(diǎn),右兒子總是可行的26重新計(jì)算右兒子的up;27if(i<n&&up>bestp{//剪枝判斷28構(gòu)造右兒子結(jié)點(diǎn)并插入隊(duì)列;}29//當(dāng)前結(jié)點(diǎn)N擴(kuò)展完畢30釋放N;從隊(duì)列中取下一擴(kuò)展結(jié)點(diǎn)N;31}//while32output(bestp,bestx);33}隊(duì)列式分支限界：

按照活結(jié)點(diǎn)先進(jìn)先出的策略進(jìn)行搜索，每一個(gè)擴(kuò)展結(jié)點(diǎn)具有相同的優(yōu)