算法的设计 分支限界法倒推法.ppt

子集和问题 问题 给定由n个不同正数组成的集合 W={w;},和正数M,求W中所有 和等于M的子集的集合 例如n=6,M=30, W={10,13,5,18,12,15} 2013-74 1of15 子集和问题 按照回溯法思想,从状态树的根结点出 发,做深度优先搜索; 为便于计算,将W中的正数按从小到大 排序; 当在某一状态A下,依次尝试加入和不加 入正数w,若A+W>M,则可停止对该 结点的搜