“让右手始终贴着左边的墙壁走”
举荐应用 递归 实现 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 <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 30;
int n=0;
int V=0;
int maxWeight=0;
int maxValue=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 = 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; i++){scanf("%d",&w[i]);
}
for(int i=0; i<n; i++){scanf("%d",&v[i]);
}
DFS(0,0,0);
printf("%d",maxValue);
return 0;
}- 给定 N 个整数（可能有正数），从中选取 K 个数，使得这 K 个数之和恰好等于一个给定的整数 X，如果有多种计划，抉择它们中元素平方和最大的一个（《算法笔记》P273 页）
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
const int maxn = 10000;
int n=0;
int k=0;
int x=0;
int maxSquare=-1;
int A[maxn];
vector<int> st;
vector<int> 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<n; i++)
{scanf("%d",&A[i]);
}
scanf("%d",&k);
scanf("%d",&x);
DFS(0,0,0,0);
printf("%d\n",maxSquare);
for(int i=0; i<st.size(); i++)
{printf("%d",st[i]);
}
return 0;
}参考书目：《算法笔记》