回溯法 01 背包问题
回溯法:是一个既带有系统性又带有跳跃性的的搜索算法。它在
包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜
索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否
肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的
系统搜索,逐层向其原先结点回溯。否则,进入该子树,继续按深度优先
的策略进行搜索。
课堂上老师已经讲解过用回溯法解决 n- 皇后问题, m- 图着色问
题以及哈密顿环问题,他们有相同的特征即问题的求解目标都是求满足约
束条件的全部可行解。而 0/1 背包是最优化问题,还需要使用限界函数
剪去已能确认不含最优答案结点的子树。
第 1 页 / 共 18 页