问题描述：
给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
n个物品中选择部分物品，可知，问题的解空间是子集树。比如物品数目n=3时，其解空间树如下图
思路：
边为1代表选择该物品，边为0代表不选择该物品。回溯搜索过程，如果来到了叶子节点，表示一条搜索路径结束，如果该路径上存在更优的解，则保存下来。如果不是叶子节点，是中点的节点（如B），就遍历其子节点（D和E），如果子节点满足剪枝条件，就继续回溯搜索子节点。
边界条件是当前递归深度到叶子节点；
此时判断是不是更优的解；
约束条件是放入当前物品到背包后，背包内物品总重量不超过背包容量，则继续搜索，直至叶子节点；
回溯点，中间节点；
提交代码
// 还未亲测，后续补充
回溯法概述：
回溯法（探索与回溯法）是一种优先搜索法，又称为试探法，按优先条件向前探索，以达到目标。但当探索到某一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
在回溯法中，每次扩大当前部分解时，都面临一个可选的状态集合，新的部分解就通过在该集合中选择构造而成，这样的状态集合，其结构就是一颗多叉树。
回溯法解题
应用回溯法求解问题时，首先应明确定义问题的解空间，该解空间应至少包含问题的一个最优解。
在定义了问题的解空间，还需要将解空间有效地组织起来，使得回溯法方便的搜索整个解空间，通常将解空间组织成树或图的形式。
确定了问题的解空间结构后，回溯法将从开始结点（根节点）出发，以深度优先的方式搜索整个解空间。
开始结点成为活结点，同时也成为扩展结点，向纵深方向搜索并移至一个新结点，这个新结点就成为一个新的活结点，并成为当前的扩展结点。
如果在当前的扩展结点不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应往回移动（回溯）至最近的一个活结点，并使其称为当前的扩展结点。
回溯法以上述工作方式递归地在解空间中搜索，直至找到所要求的解或者解空间中已无活结点为止。
运用回溯法解题的三个关键
（1）针对给定的问题，定义问题的解空间
（2） 确定易于搜索的解空间结构
（3）以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效检索。
一般情况下可以用递归函数实现回溯法，递归函数模板如下：
void BackTrace(int t){
if(t>n){
Output(x)
}
else{
for(int i=f(n,t);i<=g(n,t);i++){
x[t] = h(i);
if(Constraint(t)&&Bound(t)){
BackTrace(t+1);
}
}
}
}
t 表示递归深度，即当前扩展结点在解空间树中的深度；
n 用来控制递归深度，即解空间树的高度。
当 t>n时，算法已搜索到一个叶子结点，此时由函数Output(x)对得到的可行解x进行记录或输出处理。
用 f(n, t)和 g(n, t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号；
h(i)表示在当前扩展结点处x[t] 的第i个可选值；
函数 Constraint(t)和 Bound(t)分别表示当前扩展结点处的约束函数和限界函数。
若函数 Constraint(t)的返回值为真，则表示当前扩展结点处x[1:t] 的取值满足问题的约束条件；否则不满足问题的约束条件。若函数Bound(t)的返回值为真，则表示在当前扩展结点处x[1:t] 的取值尚未使目标函数越界，还需由BackTrace(t+1)对其相应的子树做进一步地搜索；否则，在当前扩展结点处x[1:t]的取值已使目标函数越界，可剪去相应的子树。