回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树搜索，逐层向其祖先结点回溯；否则 ，进入该子树，继续按深度优先策略搜索。
问题的解空间
用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个(最优)解。对于 n=3 时的 0/1 背包问题，可用一棵完全二叉树表示解空间，如图所示：
求解步骤
1)针对所给问题，定义问题的解空间；
2)确定易于搜索的解空间结构；
3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常用的剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。
回溯法对解空间做深度优先搜索时，有递归回溯和迭代回溯（非递归）两种方法，但一般情况下用递归方法实现回溯法。
算法描述
解 0/1 背包问题的回溯法在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。
代码：
public class Knapsack_Problem01 {
double m=100; //背包最大容量
int n=5; //物品的个数
int[] w = {10,20,30,40,50}; //第i个物品的重量
int[] v = {20,30,65,40,60}; //第i个物品的价值
int[] a = new int[n]; //记录在树中的移动路径,为1的时候表示选择该组数据，为0的表示不选择该组数据
int maxvalue = 0; //背包的最大权重值
public static void main(String[] args)
{
Knapsack_Problem01 p = new Knapsack_Problem01();
p.Search(0);
}
public void Search(int i) //i表示递归深度
{
if(i>=n)
{
CheckMax();
}
else {
a[i] = 0;
Search(i+1);
a[i] = 1;
Search(i+1);
}
}
public void CheckMax()
{
int weight = 0;
int value = 0;
for(int i=0;i<n;i++) //判断是否达到上限
{
if(a[i] == 1)
{
weight = weight + w[i];
value = value + v[i];
}
}
if(weight <= m)
{
if(value >= maxvalue)
{
maxvalue = value;
System.out.print("最大价值是：" + maxvalue +" ");
System.out.print("所选取的物品为(1代表选中，0代表不选中)： ");
for(int j=0;j<n;j++)
{
System.out.print(a[j]);
System.out.print(' ');
}
System.out.print('\n');
}
}
}
}