问题描述:背包的容量为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;
}
}
}
对于背包问题其算法代码如下:
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进制枚举要高很多。