回溯法解决01背包问题回溯法解决01背包问题1 1、算法思想、算法思想2 2、问题描述、问题描述3 3、设计实现、设计实现 回溯法解决01背包问题回溯法：是一个既带有系统性又带有跳跃性的的搜回溯法：是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其原先结点回溯。否则，为根的子树的系统搜索，逐层向其原先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。进入该子树，继续按深度优先的策略进行搜索。课堂上老师已经讲解过用回溯法解决课堂上老师已经讲解过用回溯法解决n-皇后问题，皇后问题，m-图着色问题以及哈密顿环问题，他们有相同的特征即图着色问题以及哈密顿环问题，他们有相同的特征即问题的求解目标
