“让右手始终贴着左边的墙壁走”
举荐应用递归实现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;
}参考书目：《算法笔记》
发表回复