分支界限法解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;

四 、运行结果

五 、实验小结

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

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