回溯算法理解
一、算法含义
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思路是：暴力算法的改进，在通过遍历所有路径基础上，通过回溯（往回找）筛除不可能的路径，提高效率。
二、解题步骤：
1.确定一个解空间，它包含问题的解；
2.利用适于搜索的方法组织解空间；
3.利用深度优先法搜索解空间；
4.利用剪枝（约束函数、限界函数）避免移动到不可能产生解的子空间。
三、算法框架
bool constraint(int t){};//约束函数 bool bound(int t){};//限界函数 void backtrack(int t){ if(t > n) output(x); else{ for(int i = f(n,t); i <= g(n,t);i++){ //该节点的子节点（分量的所有下一个分量）
x[t] = h(i);
if(constraint(t) && bound(t))
backtrack(t+1); }
}
}
四、例题
7-1 子集和问题 （50 分）
设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法。
输入格式:
输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。 是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。
输出格式:
输出子集和问题的解，以空格分隔，最后一个输出的后面有空格。当问题无解时，输出“No Solution!”。
输入样例:
5 10 2 2 6 5 4
输出样例:
2 2 6
代码：
#include <iostream> using namespace std; int flag =0; int s[100000]; int selec[100000]; int fin_selec[100000]; void backTrack(int target,int t,int sum ,int n){ if(flag==1)return; if (t>=n) { if (sum == target) { for (int i=0; i<n; i++) { fin_selec[i] = selec[i]; } flag = 1; return; } return; } if (sum+s[t]<=target) { selec[t]=1; sum +=s[t]; backTrack(target, t+1, sum, n); selec[t]=0; sum -= s[t]; } selec[t] =0; backTrack(target, t+1, sum, n); } int main(){ int n,target; cin>>n>>target; for (int i=0; i<n; i++) { cin>>s[i]; selec[i]=0; fin_selec[i]=0; } int sum=0; for (int i=0; i<n; i++) { sum+=s[i]; } if (sum<target) { cout<<"No Solution!"<<endl; exit(0); } backTrack(target, 0, 0, n); if (flag==1) { for (int i=0; i<n; i++) { // cout<<fin_selec[i]; if (fin_selec[i]==1) { cout<<s[i]<<" "; } } }else cout<<"No Solution!"<<endl; return 0; }
五、总结
由于对算法的不够熟悉，导致细节出问题，思维不够发散，模版很好用，再加上对约束函数限界函数的完善就是整道题的清晰思路。
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。