dfa
之前用DFS可能最多的就是树类问题，但是随着最近图论的深入，看了看相关的问题，发现问题并不局限于此；
由于之前接触过动态规划还有贪心算法，突然发现DFS和动态规划貌似有点类似，之前个人感觉可能不同的点在于两点：
1.动态规划有相关的状态转移方程，定下边界之后，就严格的按照状态转移方程来进行解决；
2.动态规划具有重叠子问题，进行逐步的计算，用小问题的解解决大问题。但是个人感觉，DFS貌似也有这种思想的体现，其具体体现的是回溯思想，所以这里脑壳还是有点转不过来；
但是我觉得以下的一位大佬总结的还是有点到位的，DFS其实也算是冬天规划的一种：
所以DFS思想不仅仅可以作为一个路径解决问题，更可以用来解决背包问题，并且用递归解决会有一个更加直观的表现；
在之前看的案例中就有这种体现；
例如：有n件物品，每件物品的重量位w[i],价值位c[i]。现在需要选出若干见物品放入一个容量V的背包中，使得选入背包的物品总重量不超过V的前提下，使得背包中的物品总价最大，并且求这个最大值；
对于这个问题，我们可以很好的规定出相关的边界；
递归边界显然是：总重量小于V，且迭代了n次，进行了2*n次选择；这里的选择很好理解，对于第i件物品，会有两种选择，放或者不放，可以类似认为像是走迷宫的两个分支，左边和右边；
因此，我们可以定义全局变量n(物品的件数),V(背包总容量),maxValue(背包内的物品最大值);
相关的函数定义可以为：
void DFS(int index,int sumW,int sumC)
其中sumW为现阶段下的总重量，sumC代表现阶段下的总价值；
void DFS(int index,int sumW,int sumC){
if(index==n){
//代表枚举n件物品完毕，递归边界
if(sumW<=V&&sumC>maxValue){
maxValue=sumC;
}
return;
}
DFS(index+1,sumW,sumC);
DFS(index+1,sumW+w[index],sumC+c[index]);
}
整体来说DFS函数如上所示，函数结尾递归表示了两种选择，即选不选第i件；
上述算法的时间复杂度为O(2^n)，表现不是很好，究其原因是其先选再判断容量，多了很多分支；
对于示例中给出的优化，为先判断在分治，会高效很多；
void DFS(int index,int sumW,int sumC){
if(index==n){
//代表枚举n件物品完毕，递归边界
return;
}
DFS(index+1,sumW,sumC);
if(sumW+w[index]<=V){
if(sumC+c[index]>ans){
ans=sumC+c[index];
}
DFS(index+1,sumW+w[index],sumC+c[index]);
}
}
这可以说是比较经典的应用场景；
还有一个示例：给定N个整数（可能有复数），从中选择K个数，使得K个整数的和正好等于一个给定的整数X；如果有多个方案，选择他们平方和中最大的一个；
这个问题其实很好的阐述了回溯的思想，也就是中间状态当回溯的时候，该如何保存的问题；
如下代码所示，temp保存了当前的最优解选项，如果回溯，则进行pop操作，当符合最优解的时候，直接赋值保存；
int n,k,x,maxSumSqu=-1,A[maxn];
//从n中选择k个数，使得平方和最大化
vector<int>temp,ans;
void DFS(int index,int nowK,int sum,int sumSqu){
if(nowK==k&&sum==x){
if(sumSqu>maxSumSqu){//如果找到最优解
maxSumSqu=sumSqu;//更新最大平方和
ans=temp;//更新最优方案
}
return;
}
if(index==n||nowK>k||sum>x)
return;
temp.push_back(A[index]);
DFS(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);
temp.pop();
DFS(index+1,nowK,sum,sumSqu);
}
这里注意一下，这个题目其实和01背包问题类似，所以如果对于普通背包问题，即可以选择重复的数字时，又该怎么办；
解决方案如下所示，和背包的状态转移类似，如果可以选择自己，则状态不变，类似的，DFS可以使得index不变，从而表示再一次选择该数字；
int n,k,x,maxSumSqu=-1,A[maxn];
//从n中选择k个数，使得平方和最大化
vector<int>temp,ans;
void DFS(int index,int nowK,int sum,int sumSqu){
if(nowK==k&&sum==x){
if(sumSqu>maxSumSqu){//如果找到最优解
maxSumSqu=sumSqu;//更新最大平方和
ans=temp;//更新最优方案
}
return;
}
if(index==n||nowK>k||sum>x)
return;
temp.push_back(A[index]);
DFS(index,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);
temp.pop();
DFS(index+1,nowK,sum,sumSqu);
}
相关阅读
转载地址：https://blog.csdn.net/ZSZ_shsf/article/details/61413645文章解释了几个简单的信噪比公式并给出了相关推导和实验分析
知识付费不同于出行或外卖行业“高频＋刚需”的应用场景，知识交易的频率相对较低，但是个性化程度非常高，未来的竞争也许会很残酷，但用户
前段时间我从网上下载了一份非常有价值的 PDF 文档，如获珍宝，但是在看的过程中，我想对它的内容编辑，加入一些属于我自己的想法、笔记，
每日晨会的内容和方式： 可以根据晨会参与者的不同，是否在同一物理地点办公等因素，来制定有针对性的沟通内容和方式。 供应商团队
最想说的还是注意身体吧。工作之后才发现，原来身体真的会累垮。大学时候的放纵，现在都会还的。 选择比努力更重要，这个不多说，大家都