背包问题之回溯法

问题描述：背包的容量为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进制枚举要高很多。