回溯法是一个既带有系统性又带有跳跃性的搜索算法。

它在包含问题的所有解的解空间树中按照深度优先的策略，从根节点出发搜索解空间树。

算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其原先节点回溯。

否则，进入该子树，继续按深度优先的策略进行搜索。

运用回溯法解题通常包含以下三个步骤：
∙针对所给问题，定义问题的解空间；
∙确定易于搜索的解空间结构；
∙以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
在0／1背包问题中，容量为M的背包装载。

从n个物品中选取装入背包的物品，物品i的重量为Wi，价值为Pi。

最佳装载指装入的物品价值最高，即∑PiXi(i=1..n)取最大值。

约束条件为∑WiXi ≤M且Xi∈[0,1](1≤i≤n)。

在这个表达式中，需求出Xi的值。

Xi=1表示物品i装入背包，Xi＝0表示物品i不装入背包。

∙即判断可行解的约束条件是：∑WiXi≤M（i=0..n），Wi>0,Xi∈[0,1](1≤i≤n)
∙目标最大值：max∑PiXi（i=0..n-1）,Pi>0,Xi=0或1（0≤i<n）
0/1背包问题是一个自己选取问题，适合于用子集树表示0／1背包问题的解空间。

在搜索解空间树时，只要左儿子节点是一个可行节点，搜索就进入左子树，在右子树中有可能包含最优解才进入右子树搜索，否则将右子树剪去。

程序分析：
将物品个数，每个物品体积／价值输入，计算总物品体积S，输入背包体积V，如果V<0或者V>S则前置条件错误，即背包体积输入错误，否则顺序将物品放入背包。

假设放入前i件物品，背包没有装满，继续选取第i+1件物品，若该物品“太大”不能装入，则弃之继而选取下一件直到背包装满为止；如果剩余物品中找不到合适物品以填满背包，则说明“刚刚”装入的第i件
物品不合适，应将i拿出，继续从i＋1及以后的物品中选取，如此重复，直到找到满足条件的解。

回溯求解，物品放入的规则是“后进先出”，所以要用栈存储符合条件的解。

剪枝（限界）函数
设当前剩余物品价值总和为r，当前结点x价值为cp，当前x结点上界函数值为bp。

L为当前已搜索到的答案结点中受益的最大值，当cp+r=bp<L时可剪去以X为根的子树。

计算右子树中解上界方法是将剩余物品按单位重量价值排序，一次放入物品直至装不下为止，再装入部分未装入物品直至装满背包，由此得到的价值是右子树解上界。

递归方式：
顺序方式：无剪枝函数：
有剪枝函数：。