DFS搜索

背包问题

背包有容量（重量）每件物品有自己的价值和重量物品取或不取两种情况 const int maxn = 30; int n, V, maxValue = 0;//物品件数n、背包容量V、最大价值maxValue int w[maxn], c[maxn];//每件物品的重量和价值 void dfs(int index, int sumW, int sumC) { if (index == n) { if (sumW<V && sumC>maxValue) { maxValue = sumC;//更新最大价值 } return; } dfs(index + 1, sumW, sumC);//不选index dfs(index + 1, sumW + w[index], sumC + c[index]);//选index }

这种写法就是遍历所有情况，取或不取 其实在取物品之前可以提前判断是否超重

void dfs(int index, int sumW, int sumC) { if (index == n) { return; } dfs(index + 1, sumW, sumC);//不选index //选index if (sumW + w[index] <= V) { if (sumC + c[index] > maxValue) { maxValue = sumC + c[index]; } dfs(index + 1, sumW + w[index], sumC + c[index]); } //dfs(index + 1, sumW + w[index], sumC + c[index]);//选index }

从n个数中选出m个数进行全排列

#include<vector> #include<iostream> using namespace std; const int maxn = 100; vector<int> re; int g[maxn] = { 2,5,6,7 }; int vis[maxn] = { 0 }; int n = 4, m = 3; void dfs(int index) { if (index == m) { for (int i = 0; i < re.size(); i++) { cout << re[i] << " "; } cout << endl; return; } for (int i = 0; i < n; i++) { if (vis[i] == 0) { vis[i] = 1; re.push_back(g[i]); dfs(index + 1); re.pop_back(); vis[i] = 0; } } } int main() { dfs(0); return 0; }

寻找平方和最大数

const int maxn = 100; //序列A中选k个数使得和为x，最大平方和为maxSumSqu int n, k, x, maxSumSqu = -1, A[maxn]; //temp存放临时方案，ans存放平方和最大的方案 vector<int> temp, ans; //当前处理index号整数，当前已选整数个数为nowK //当前和为sum，平方和为sumSqu void dfs(int index,int nowK,int sum,int sumSqu) { if (nowK == k && sum == x) { //找到了k个数和为x if (sumSqu > maxSumSqu) { maxSumSqu = sumSqu; ans = temp; } return; } if (index == n || nowK > k || sum > x)return; //选index号 temp.push_back(A[index]); dfs(index + 1, nowK + 1, sum + A[index], sumSqu + A[index] * A[index]); temp.pop_back(); //不选index号 dfs(index + 1, nowK, sum, sumSqu); }