3358www.Sina.com/导线测量类似于树根导线测量。 是树根遍历的普及，在算法竞赛和试验中经常被使用。 在优化图算法时，也非常方便。 就像在迷路的过程中，遇到岔道时“深度优先搜索”成为前进的关键词一样。
深度优先搜索变为深度，每次陷入僵局都代表完整路径的形成。 即不碰到死胡同就不回头
使用递归可以很好地进行深度优先的检索。 当然也可以使用非递归方法实现DFS，但非递归方法一般比递归方法麻烦。 使用递归时，系统调用走遍所有路径来存储递归中各层的状态，所以使用递归实现DFS的本质其实是堆栈。
下面举例说明。 读者需要理解其中包含的DFS思想，并学习编写本例的代码。
有n件物品，每件物品的重量为w[i]，价值为c[i]。 现在需要选择一些物品放在容量为V的背包里。 在不超过放入背包的物品的重量和容量v的前提下，需要使背包中物品的价值之和最大化，求出最大的价值。 (1n20 )
在这个问题上，需要从n件物品中选择几件物品放入背包，使它们的价值之和最大化。 这样的话，每个东西都有选择和不选择两种选择，那就是“旁道”。 那么，“死胡同”是什么呢？ ——主题要求选定项的总重量不超过v，因此如果选定项的总重量超过v，将会出现“僵局”，您必须返回最近的“岔道”。
很明显，由于每次都要选择项目，因此DFS函数的参数必须记录当前正在处理的项目编号index。 因为主题包含物品的重量和价值，所以在处理当前物品之前，还需要用于记录选定物品的总重量sumW和总价值sumC的参数。 DFS函数看起来是这样的。
voidDFS(intindex，int sumW，int sumC )…}因此，如果选择不放入index号的东西，sumW和sumC不会改变。 接下来处理index 1号的东西。 即，DFS )面向索引1、sumW、sumC，另一方面，在选择放入索引号的物品的情况下，sumW增加当前物品的重量w[index]，sumC增加当前物品的价值c[index]
index成长为n后，意味着处理了n个物品。 (因为物品的下标从0到n-1 )，此时记录的sumW和sumC是所选物品的总重量和总价值。 如果sumW小于或等于v，且sumC大于记录最大总价值的全局变量maxValue，则当前选择将获得更大的价值，并在sumC中更新maxValue。
以下代码体现了上述思想。 请注意“旁道”和“死胡同”是如何出现在代码中的。
#includecstdioconst int maxn=30； int n，v，maxValue=0； //物品数量n、背包容量v、最大价值maxValueint w[maxn]、c[maxn]； //w[i]是各道具的重量，c[i]是各道具的价值//DFS，index是现在正在处理的道具号码//sumW和sumC分别是现在的总重量和现在的总价值voidDFS(intindex，int summ ) //道口DFS(index1，sumW，sumC )； 不选择索引项DFS (索引，sumW w[index]，sumC c[index] )； 选择索引号(} int main ) )扫描)、n、v )； for(intI=0； in； I ) scanf('%d '，w[i]； //每个物品的重量(for(intI=0； in； I ) scanf('%d '，c[i]； //每个物品的价值(DFS (0，0，0 )；//初始化为第0个项目，当前总重量和总价值均为0printf('%dn”，maxValue )； 返回0； }输入数据：
5 83 5 1 2 24 5 2 1 3输出结果：
请注意，上面的代码的复杂性为O(2)，因为每个项有两种选择，而且看起来不太出色。 但是，通过优化算法，可以使随机数据的表示更加高效。 在上述代码中，总是在确定所有n个物品的选择后更新最大价值，但实际上忽略了背包容量不超过v的特征。 也就是说，对sumW的判断可以完全进入“旁道”，只有在sumWv的时候才能进入旁道。 这个非常有效率。 代码如下，深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法。
了DFS： #include<cstdio>const int maxn = 30;int n,V,maxValue = 0;//物品件数n，背包容量v，最大价值maxValueint w[maxn],c[maxn];//w[i]为每一件物品的重量，c[i]为每件物品的价值//DFS，index为当前处理的物品编号//sumW和sumC分别为当前总重量和当前总价值void DFS(int index,int sumW,int sumC) {if(index == n){//已经完成对n件物品的选择（死胡同） return; } //岔道口DFS(index+1,sumW,sumC);//不选第index件物品 //只有加入第index件物品后未超出容量V，才能继续 if(sumW+w[index]<=V) {if(sumC+c[index]>maxValue)maxValue = sumC+c[index];//更新最大价值maxValue }DFS(index+1,sumW+w[index],sumC+c[index]);//选第index件物品 } int main(){scanf("%d%d",&n,&V);for(int i=0;i<n;i++){scanf("%d",&w[i]);//每件物品的重量 }for(int i=0;i<n;i++){scanf("%d",&c[i]);//每件物品的价值 }DFS(0,0,0);//初始化为第0件物品、当前总重量和总价值均为0 printf("%dn",maxValue);return 0;}可以看到，原先第二条岔路是直接进入的，但是这里先判断加入第index件物品后能否满足容量不超过V的要求，只有当条件满足时才更新最大价值以及进入这条岔路，这样可以降低计算量，使算法在数据不极端时有很好的表现。这种通过题目条件的限制来节省DFS计算量的方法称作剪枝（前提是剪枝后算法仍然正确）。剪枝是一门艺术，学会灵活运用题目中给出的条件，可以使得代码的计算量大大降低，很多题目甚至可以使时间复杂度下降好几个等级。
例如这样一个问题： 给定N个整数(可能有负数)，从中选择K个数，使得这K个数之和恰好等于一个给定的整数X：如果有多种方案，选择它们中元素平方和最大的一个。数据保证这样的方案唯一。例如，从4个整数{2,3,3,4}中选择2个数，使它们的和为6，显然有两种方案{2,4}与(3,3}，其中平方和最大的方案为{2,4}。
与之前的问题类似，此处仍然需要记录当前处理的整数编号index；由于要求恰好选择K个数，因此需要一个参数nowK来记录当前已经选择的数的个数；另外，还需要参数sum和sumSqu分别记录当前已选整数之和与平方和。于是DFS就是下面这个样子：
void DES(int index,int nowK,int sum, int sumSqu){ ...}此处主要讲解如何保存最优方案，即平方和最大的方案。首先，需要一个数组temp，用以存放当前已经选择的整数。这样，当试图进入“选index号数”这条分支时，就把A[index]加入temp中；而当这条分支结束时，就把它从temp中去除，使它不会影响“不选 index号数”这条分支。接着，如果在某个时候发现当前已经选择了K个数，且这K个数之和恰好为x时，就去判断平方和是否比已有的最大平方和 maxSumSqu还要大：
如果确实更大，那么说明找到了更优的方案，把temp赋给用以存放最优方案的数组ans。这样，当所有方案都枚举完毕后，ans存放的就是最优方案， maxSumSqu存放的就是对应的最优值
输入：
4 2 62 3 3 4输出：
2 4程序代码：
#include<cstdio>#include<vector>using namespace std;const int maxn = 30;//序列A中n个数选k个数使得和为x，最大平方和为maxSumSqu int n,k,x,maxSumSqu = -1,A[maxn];//temp存放临时方案，ans存放平方和最大的方案vector<int> temp, ans;//当前处理index号整数，当前已选取的整数个数时nowK//当前已选整数之和为sum，当前已选整数平方和为sumSquvoid DFS(int index,int nowK,int sum,int sumSqu){if(nowK == k && sum == x){//找到k个数的和为x if(sumSqu>maxSumSqu){//如果比当前找到更优 maxSumSqu = sumSqu;//更新最大平方和 ans = temp;//更新最优方案 }return;}//已经处理完n个数，或者超过k个数，或者和超过x，返回if(index == n||nowK>k||sum>x)return ;//选index号数temp.push_back(A[index]);DFS(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);temp.pop_back();//不选index号数DFS(index+1,nowK,sum,sumSqu); } int main(){scanf("%d%d%d",&n,&k,&x);for(int i=0;i<n;i++){scanf("%d",&A[i]);}DFS(0,0,0,0);for(vector<int>::iterator it = ans.begin();it!=ans.end();it++){printf("%d ",*it);} return 0;}运行结果：
上面这个问题中的每个数都只能选择一次，现在稍微修改题目：假设N个整数中的每个都可以被选择多次，那么选择K个数，使得K个数之和恰好为X。例如有三个整数1、4、7，需要从中选择5个数，使得这5个数之和为17。显然，只需要选择3个1和2个7，即可得到17。
这个问题只需要对上面的代码进行少量的修改即可。由于每个整数都可以被选择多次，因此当选择了 index 号数时，不应当直接进入 index+1 号数的处理。显然，应当能够继续选择 index 号数，直到某个时刻决定不再选择 index 号数，就会通过“不选 index号数”这条分支进入 index+1 号数的处理。因此只需要把“选index号数”这条分支的代码修改为DFS(index,nowK+1,sum+A[index],sumSqu+A[index]*A[index]); 即可。
程序代码：
#include<cstdio>#include<vector>using namespace std;const int maxn = 30;//序列A中n个数选k个数使得和为x，最大平方和为maxSumSqu int n,k,x,maxSumSqu = -1,A[maxn];//temp存放临时方案，ans存放平方和最大的方案vector<int> temp, ans;//当前处理index号整数，当前已选取的整数个数时nowK//当前已选整数之和为sum，当前已选整数平方和为sumSquvoid DFS(int index,int nowK,int sum,int sumSqu){if(nowK == k && sum == x){//找到k个数的和为x if(sumSqu>maxSumSqu){//如果比当前找到更优 maxSumSqu = sumSqu;//更新最大平方和 ans = temp;//更新最优方案 }return;}//已经处理完n个数，或者超过k个数，或者和超过x，返回if(index == n||nowK>k||sum>x)return ;//选index号数temp.push_back(A[index]);DFS(index,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);temp.pop_back();//不选index号数DFS(index+1,nowK,sum,sumSqu); } int main(){scanf("%d%d%d",&n,&k,&x);for(int i=0;i<n;i++){scanf("%d",&A[i]);}DFS(0,0,0,0);for(vector<int>::iterator it = ans.begin();it!=ans.end();it++){printf("%d ",*it);} return 0;}运行结果：
微信扫码关注李歘歘，获取更多的学习资料，联系作者：