DFS学习心得——0

学习心得——0"/>

DFS学习心得——0

1 题目 0-1背包问题

有n件物品，每件物品的重量为w[i],价值为c[i]。现在需要选出若干件物品放入一个容量为V的背包中，使得在选入背包的物品重量和不超过容量V的前提下，让背包中物品的价值之和最大，求最大价值(1<=n<=20)

Sample Input：
5 8 			//5件物品，背包容量为8
3 5 1 2 2	//重量
4 5 2 1 3	//价值Sample Output：
10

• 思路
• 递归（系统栈实现）
• 岔路口（递归式）：选择该物品和不选择该物品
• 死胡同（递归边界）：选择的物品总重量超过V

参考代码

#include <cstdio>const int MAXN = 30;
int w[MAXN],c[MAXN];
int n, V, maxValue;void DFS(int index, int sumW, int sumC){//当前的物件编号、总重量、总价值if(index == n){//递归边界（死胡同），已完成对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物件
}int main(int argc, char const *argv[])
{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);//初始为零物件，当前总质量和总价值为0printf("%d\n", maxValue);return 0;
}

优化：剪枝（通过题目条件的限制节省DFS计算量）

优化后的代码

#include <cstdio>const int MAXN = 30;
int w[MAXN],c[MAXN];
int n, V, maxValue;void DFS(int index, int sumW, int sumC){//当前的物件编号、总重量、总价值if(index == n) return;DFS(index + 1, sumW, sumC);//剪枝，只有加入重量后未超过V，才加入Vif(sumW + w[index] <= V){if(sumC + c[index] > maxValue) maxValue = sumC + c[index];DFS(index + 1, sumW + w[index], sumC + c[index]);}
}int main(int argc, char const *argv[])
{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);//初始为零物件，当前总质量和总价值为0printf("%d\n", maxValue);return 0;
}

2 问题

常见DFS问题

• 给定一个序列，枚举这个序列的所有子序列（可以不连续）
• 枚举N个整数选择K个数的所有方案。

题目描述：
给定N个整数（可能有负数），从中选择K个数（这K个数不重复），使得这K个数之和恰好等于一个给定的整数X；如果有多种方案，选择它们中元素平方和最大的一个。数据保证这样的方案唯一。

Sample Input:
4 2 6		//4个整数 选2个 使得之和为6
2 3 3 4		//4个整数
Sample Output:
2 4		//平方和最大的一个

参考代码：

#include <cstdio>
#include <vector>using std::vector;const int MAXN = 100010;vector<int>ans, temp;//分别存放最大方案和临时方案
int N, K, X, maxSumSqu = -1;
//分别存放总数N，选择的个数K，等于的值X，最大平方数maxSumSqu
int A[MAXN];//输入的数据void DFS(int index, int nowok, int sum, int sumSqu){
//当前处理的index号整数，找到的个数nowork，找到数的和sum、平方数sumSquif(nowok == K && sum == X){//找到k个数，且和为Xif(sumSqu > maxSumSqu){//比当前找的更优，更新maxSumSqu = sumSqu;ans = temp;//更新最优方案}return;}//分别表示：已处理完n个数，超过k的个数，超过xif(index == N|| nowok > K || sum > X) return;//选index号整数temp.push_back(A[index]);//不可以重复选择DFS(index + 1, nowok + 1, sum + A[index], sumSqu + A[index] * A[index]);//可以重复选择index号整数//DFS(index , nowok + 1, sum + A[index], sumSqu + A[index] * A[index]);//不选index号整数temp.pop_back();DFS(index + 1, nowok, sum, sumSqu);
}int main(int argc, char const *argv[])
{scanf("%d%d%d", &N, &K, &X);for (int i = 0; i != N; ++i){scanf("%d", &A[i]);}DFS(0, 0, 0, 0);for (vector<int>::const_iterator it = ans.begin(); it != ans.end(); ++it){if(it != ans.end() && it != ans.begin()) printf(" ");printf("%d", *(it));}printf("\n");return 0;
}

题目变式：
假设N个整数的每一个都可以被选择多次，那么选择K个数，使得K的数值和恰好为X。

Sample Input:
3 5 17 			//3个整数 选5个 使得之和为17
1 4 7       		//3个整数
Sample Output:
2 4		//平方和最大的一个

参考代码：

#include <cstdio>
#include <vector>using std::vector;const int MAXN = 100010;vector<int>ans, temp;//分别存放最大方案和临时方案
int N, K, X, maxSumSqu = -1;
//分别存放总数N，选择的个数K，等于的值X，最大平方数maxSumSqu
int A[MAXN];//输入的数据void DFS(int index, int nowok, int sum, int sumSqu){
//当前处理的index号整数，找到的个数nowork，找到数的和sum、平方数sumSquif(nowok == K && sum == X){//找到k个数，且和为Xif(sumSqu > maxSumSqu){//比当前找的更优，更新maxSumSqu = sumSqu;ans = temp;//更新最优方案}return;}//分别表示：已处理完n个数，超过k的个数，超过xif(index == N|| nowok > K || sum > X) return;//选index号整数temp.push_back(A[index]);//不可以重复选择//DFS(index + 1, nowok + 1, sum + A[index], sumSqu + A[index] * A[index]);//可以重复选择index号整数DFS(index , nowok + 1, sum + A[index], sumSqu + A[index] * A[index]);//不选index号整数temp.pop_back();DFS(index + 1, nowok, sum, sumSqu);
}int main(int argc, char const *argv[])
{scanf("%d%d%d", &N, &K, &X);for (int i = 0; i != N; ++i){scanf("%d", &A[i]);}DFS(0, 0, 0, 0);for (vector<int>::const_iterator it = ans.begin(); it != ans.end(); ++it){if(it != ans.end() && it != ans.begin()) printf(" ");printf("%d", *(it));}printf("\n");return 0;
}