8.1 深度优先搜索(DFS)
深度优先搜索会走遍所有路径，并且每次走到死胡同就代表一条完整路径的形成。这就是说，深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法。
例子（背包问题）：
有n件物品，每件物品的重量w[i]，价值为c[i]。现在需要选出若干件物品放入一个容量为V的背包中，使得在选入背包的物品重量和不超过容量V的前提下，让背包中物品的价值之和最大，求最大价值。（1<= n <= 20)
#include<cstdio> const int maxn = 30; int n,V,maxValue = 0; //物品件数n，背包容量V，最大价值maxValue int w[maxn],c[maxn]; //w[i]为每件物品的重量，c[i]为每件物品的价值 //DFS,index为当前处理的物品编号 //sumW和sumC分别为当前总重量和当前总价值 void DFS(int index,int sumW,int sumC){ if(index == n){ //已经完成对n件物品的选择（死胡同） if(sumW <= V && sumC > maxValue){ maxValue = sumC; //不超过背包容量时更新最大价值maxValue } return; } //岔道口 DFS(index+1,sumW,sumC); //不选第index件物品 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); printf("%d\n",maxValue); return 0; }
上面的代码的复杂度为O(2^n),这看起来不是很优秀。可以改成如下代码：
void DFS(int index,int sumW,int sumC){ if(index == n){ return; //已经完成对n件物品的选择 } DFS(index + 1,sumW,sumC);//不选第index件物品 //只有加入第index件物品后未超过容量V，才能继续 if(sumW + w[index] <= V){ if(sumC + c[index] > ans){ ans = sumC + c[index]; } DFS(index+1,sumW + w[index],sumC + c[index]); //选第index件物品 } }
原文：https://www.cnblogs.com/coderying/p/12262540.html