分支界限法解0-1背包问题实验报告 下载本文

//非叶子结点,递归调用Bound函数计算上界 if(icw+w[i]<=c&&Bound(i+1,aa->cw+w[i],aa->cp+p[i])>(float)lbestp) { ubb=Bound(i,aa->cw+w[i],aa->cp+p[i]); addnode(nnoder(aa,1,ubb));//将结点加入到优先队列中 } ubb=ubb=Bound(i,aa->cw,aa->cp); if(ubb>lbestp) addnode(nnoder(aa,0,ubb)); } } display(); }

int main() { int c,n; int i=0; int *p; int *w; cout<>n; cout<>c; cout<>w[i]; cout<>p[i]; Knap knbag(p,w,c,n); knbag.solvebag(); getch();

}

return 0;

四 、运行结果

五 、实验小结

回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。