算法设计与分析 课件 8.3-分支限界 - 典型应用 - 0-1背包问题

算法设计与分析分支限界—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}队列式分支限界：

按照活结点先进先出的策略进行搜索，每一个扩展结点具有相同的优