0-1背包问题（回朔法搜索子集树）

将解空间用一颗完全二叉树表示，用回朔法搜索这颗树：

解法1：建立了一个完全二叉树（称子集树），结点中带有需要的信息，深度优先遍历这颗二叉树（递归方法），

找到最优解。

困难：如何记录当前的路径？

解决方案：1、设置一个栈

2、在递归调用“深度优先遍历左子树”之前，将0压入栈；在递归调用“深度优先遍历右子树”之前，将1压入栈

3、当递归调用出来后，将栈顶元素弹出

这样到了页结点的时候，栈中的元素就是一个解

解法2：（巧妙）不需要建立树的代码，只需要用一个数组存放访问路径，核心代码如下：

void  Backtrack( int  t)
... {
        if(t>n) Output();
        else
        ...{
              for (int i=0;i<=1;i++)
              ...{
                    path[i]与path[t]交换;   
                    if (Constraint()&&Bound(t))              Backtrack(t+1);          
              }
        }
}

递归到最后一层时，数组path中的值（0，1序列）就是这一趟的解