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

算法设计与分析

分支限界—0-1背包问题;?;解空间：{(0,0,0),(0,0,1),…,(1,1,1)}

解空间树：;算法设计：

结点的价值上界up：得到当前结点可能得到的最大价值

先进先出队列：按照入队的顺序进行活结点的扩展

约束条件：已装包物品重量和=c,即cw=c，用于判断结点是否能产生可行解

限界条件：upbestp，用于决定是否能得到最优解

剪枝：对于非可行解和非最优解一律剪枝;;填空题：

对于n=3,背包容量C=30，物品价值v=(40,27,24)，物品重量w=(20,15,15)的实例而言，初始时，价值上界up值为（）;;;输入：c,n,w[],p[]

输出：bestp,bestx[]

1Knapsack(c,n,w,v){

2计算所有物品的总重量W和总价值V;

3if(W=c){

4bestp=V;

5bestx[1..n]=1;//物品全部装包

6return;

7}

8将物品按单位价值非增排序;计算初始up;

9创建队列并初始化;

10bestp=0;bestx[1.n]=0;

11创建并初始化第一个结点N；

12//N入队;出队N;//这两个操作可省略

13while(N存在){//N不会是叶子结点

14//扩展左儿子,即考虑下一物品装包

15inti,cp,cw,up;i=N.l+1;

16cw=N.cw+w[i];;17if(cw=c){//左儿子为可行结点

18cp=N.cp+v[i];up=N.up;

19if(cpbestp){//发现新的最优解

20bestp=cp;bestx[1..n]=N.x[1..n];

21bestx[i]=1;}//物品i+1装包

22if(inupbestp){//剪枝判断

23构造左儿子结点并插入队列;}

24}

25//扩展右儿子结点,右儿子总是可行的

26重新计算右儿子的up;

27if(inupbestp{//剪枝判断

28构造右儿子结点并插入队列;}

29//当前结点N扩展完毕

30释放N;从队列中取下一扩展结点N;

31}//while

32output(bestp,bestx);

33};队列式分支限界：

按照活结点先进先出的策略进行有哪些信誉好的足球投注网站，每一个扩展结点具有相同的优先级。