背包问题之回溯法
问题描述：背包的容量为C，现有N件物品，价格分别为p[0],p[1]......p[n-1].重量分别为：w[0],w[1]......w[n-1].从N件物品中选择任意个放入背包中，使得物体的价值最大并且总重量不超过背包的容量C。
采用数学语言描述如下：
在 w[0]*x[0] + w[1] *x[1]+....... +w[n-1]*x[n-1] < C, x[i] = 0 或1 的条件下
求 p[0]*x[0] + p[1] *x[1]+....... +p[n-1]*x[n-1] 的最大值。
回溯法类其实也算枚举法的一种，但在搜索过程中，一般使用递归来完成。
回溯法的基本思想
对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。 这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大 提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些 不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。
回溯法中，首先需要明确下面三个概念：
（一）约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。
（二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。
（三）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。
利用回溯法解题的具体步骤
首先，要通过读题完成下面三个步骤：
(1)描述解的形式，定义一个解空间，它包含问题的所有解。
(2)构造状态空间树。
(3)构造约束函数（用于杀死节点）。
然后就要通过DFS思想完成回溯，伪代码如下：
void BackTrack(int depth)
{
if(depth > maxDepth) //已经到最大深度
{
if(solution is target)
save solution;
return;
}
for (int i =0;i<TotalExpendNode;++i)
{
if(currentNode is searchable) //当前结点满足约束条件
{
do something;
BackTrack(depth+1);
undo something;
}
}
}
对于背包问题其算法代码如下：
- #include <iostream>
- #include <vector>
- using namespace std;
- class PackBackTrack
- {
- protected:
- vector<int> m_p; //N个背包的价格
- vector<int> m_w; //N个背包的重量
- int m_c; //背包的容量
- int m_num; //物品的件数
- int bestValue; //背包最大价值
- int currentValue; //当前背包中物品的价值
- int currentWeight; //当前背包中物品的重量
- private:
- //辅助函数，用于回溯搜索
- void BackTrack(int depth)
- {
- if(depth >= m_num) //达到最大深度
- {
- if(bestValue < currentValue) //保存最优解
- bestValue = currentValue;
- return ;
- }
- if(currentWeight +m_w[depth] <= m_c) //是否满足约束条件
- {
- currentWeight += m_w[depth];
- currentValue += m_p[depth];
- //选取了第i件物品
- BackTrack(depth+1); //递归求解下一个结点
- //恢复背包的容量和价值
- currentWeight -= m_w[depth];
- currentValue -= m_p[depth];
- }
- //不取第i件物品
- BackTrack(depth+1);
- }
- public:
- //构造函数
- PackBackTrack();
- PackBackTrack(vector<int>& p,vector<int>& w, int c,int n)
- :m_p(p),m_w(w),m_c(c),m_num(n)
- {
- bestValue =0;
- currentValue =0;
- currentWeight =0;
- }
- //获取背包内物品的最大值
- int GetBestValue()
- {
- BackTrack(0);
- return bestValue;
- }
- };
- int main(void)
- {
- //测试程序
- int n;
- int c;
- cout << "请输入物品的件数" << endl;
- cin >>n;
- cout << "请输入背包的容量" << endl;
- cin >>c;
- vector<int> w(n);
- vector<int> p(n);
- cout << "请输入物品的重量:" << endl;
- for(int i=0;i<n;++i)
- cin >> w[i];
- cout << "请输入物品的价格:" << endl;
- for(int j=0;j<n;++j)
- cin >> p[j];
- PackBackTrack pack(p,w,c,n);
- int bestValue = pack.GetBestValue();
- cout << "背包内的物品的最大价值为：" << bestValue << endl;
- return 0;
- }
小结：回溯法作为一种穷举方法，可以使用约束函数来排除一些不可能的结点。虽然不理论上此算法在理论上最坏的情况下，复杂度仍为2^n,但在实际实验中，其搜索效率比上一次使用的2进制枚举要高很多。