算法分析及设计分支限界法.ppt

第6章 分支限界法;6.1 分支限界法的基本思想;6.1 分支限界法的基本思想;6.1 分支限界法的基本思想;例如考虑n=3时0-1背包问题其中w=[16,15,15], p=[45,25,25],c=30;队列分支限界法;接下来C成为当前的扩展结点它的2个儿子结点F和G 均为可行结点因此被加入到活结点队列中;从根结点A开始用一个极大堆表示活结点表的优先队列;扩展结点E得到2个叶结点J和KJ是不可