【算法笔记-深度优先搜索】“让右手始终贴着右边的墙壁走”
推荐使用递归实现DFS，使用递归的时候系统会调用系统栈，因此用递归来实现DFS的本质还是栈
vector常用函数：
| 函数 | 功能 | 时间复杂度 |
|---|---|---|
| push_back(x) | 在vector后面添加一个元素 | O(1) |
| pop_back() | 删除vector的尾元素 | O(1) |
| size() | 获得vector的元素个数 | O(1) |
| clear() | 清空vector中的所有元素 | O(N)，N为vector元素个数 |
| insert(it,x) | 向vector的任意迭代器it处插入一个元素x | O(N) |
| erase(it) | 删除迭代器it处的元素 | O(N) |
| erase(first,last) | 删除[first,last)内的所有元素 | O(N) |
- 背包问题求解注意点（《算法笔记》P272页）
#include
#include
#include
using namespace std;
const int maxn = 30;
int n=0;
int V=0;
int maxWeight=0;
int maxValue=https://www.it610.com/article/0;
int w[maxn];
int v[maxn];
void DFS(int index,int sumW,int sumV){
if(index==n){
return;
}
DFS(index+1,sumW,sumV);
if(sumW+w[index]<=maxWeight){//if条件里是<=，等于号不能漏，否则会漏解，可能要完第index号物品后，背包满了，且恰好价值最大
if(sumV+v[index]>maxValue){
maxValue = https://www.it610.com/article/sumV+v[index];
}
DFS(index+1,sumW+w[index],sumV+v[index]);
}}int main()
{
scanf("%d%d",&n,&maxWeight);
for(int i=0;
i - 给定N个整数（可能有负数），从中选取K个数，使得这K个数之和恰好等于一个给定的整数X，如果有多种方案，选择它们中元素平方和最大的一个（《算法笔记》P273页）
#include
#include
#include
using namespace std;
const int maxn = 10000;
int n=0;
int k=0;
int x=0;
int maxSquare=-1;
int A[maxn];
vector st;
vector temp;
void DFS(int index,int nowk,int sum,int sumSqu)//第二个参数nowK（当前已选整数个数）容易漏写
{
//死胡同1
if(nowk == k && sum == x)
{
if(sumSqu>maxSquare)
{
maxSquare = sumSqu;
st = temp;
}
return;
}
//死胡同2
if(index == n || nowk >k || sum>x)
////index==n容易写成index==n-1,第n-1个数是存在的，不能被返回
{
return;
}//岔路口
temp.push_back(A[index]);
DFS(index+1,nowk+1,sum+A[index],sumSqu+A[index]*A[index]);
temp.pop_back();
DFS(index+1,nowk,sum,sumSqu);
}int main()
{
scanf("%d",&n);
for(int i=0;
i
参考书目：《算法笔记》
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
