【DFS专题】

DFS专题

• • 1.背包问题
  • • 1.1【算法改进】
    • 1.2【总结】
  • 2.从N个数中选择K个数(每个数只能被选1次)
  • 3.从N个数中选择K个数(每个数可以被选多次)

1.背包问题

/*
题目描述：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。1<=N<=20
第 i 件物品价值是 v[i]，重量是 w[i]。
求解将哪些物品装入背包，可使这些物品的重量和不超过背包容量V，且总价值最大。
输出最大价值
*/

#include
using namespace std;
const int maxn = 30;
int N, V, max_value = 0;
int weight[maxn], value[maxn];
//DFS--参数设置：index记录当前处理的物品编号；sumw和sumv分别记录当前总重量和总价值
void DFS(int index, int sumw, int sumv) {
	//"死胡同"，即递归出口
	if (index == N) { //已经对这N件物品都做了选或不选的决定，或者理解为，已经遍历了一条完整的路径
		if (sumw <= V && sumv > max_value)
			max_value = sumv; //更新最优路径的结果--即最大价值
		return;
	}
	//"岔道口"，选or不选
	DFS(index + 1, sumw, sumv);//不选择index处的物品-->已经做了不选的决定，之后需要继续对下一件做选择-->index+1
	DFS(index + 1, sumw + weight[index], sumv + value[index]);//选择index处的物品
}

int main() {
	//获取数据
	cin >> N >> V;
	for (int i = 0; i < N; i++)
		cin >> weight[i];
	for (int i = 0; i < N; i++)
		cin >> value[i];
	//调用DFS
	DFS(0, 0, 0);
	cout << max_value << endl;
	return 0;
}

1.1【算法改进】

以上，对于每一件物品都有选或者不选两种选择，算法复杂度为O(2^n)；上述代码是在每次遍历完一条完整路径后再做是否满足<=V以及是否需要更新max_value的判断，但其实可以在每次做选择期间进行是否不超过容量的判断，对于中途不满足<=V的可以进行“剪枝”，直接终断往这条路径继续遍历，从而一点程度上提高效率。

#include
using namespace std;
const int maxn = 30;
int N, V, max_value = 0;
int weight[maxn], value[maxn];

//改进后的版本
void DFS(int index, int sumw, int sumv) {
	//出口
	if (index == N)
		return;
	DFS(index + 1, sumw, sumv);//不选index处的物品
	//选择index处的物品，但选择前先进行容量是否满足要求的判断，如果不满足，则中断---不再index+1，不用进行任何 *** 作
	if (sumw + weight[index] <= V) {
		if (sumv + value[index] > max_value)
			max_value = sumv + value[index];
		DFS(index + 1, sumw + weight[index], sumv + value[index]);
	}
}

int main() {
	//获取数据
	cin >> N >> V;
	for (int i = 0; i < N; i++)
		cin >> weight[i];
	for (int i = 0; i < N; i++)
		cin >> value[i];
	//调用DFS
	DFS(0, 0, 0);
	cout << max_value << endl;
	return 0;
}

1.2【总结】

以上解决背包问题的算法，可以解决选择或不选择的一类问题—枚举从N个整数中选择K个数的所有选择方案。以下为此类问题的一些变式，都可以使用DFS解决。

2.从N个数中选择K个数(每个数只能被选1次)

/*
给定N个整数（可能有负数），从中选择K个数，使得这K个数之和恰好等于一个给定的整数X；
如果有多种方案，选择它们中元素平方和最大的一个。数据保证这样的方案唯一。
例如，从4个整数{ 2，3，3，4 }中选择2个数，使它们的和为6，显然有两种方案{ 2，4 }与{ 3，3 }，其中平方和最大的方案为{ 2，4 }。
*/

#include
#include
using namespace std;
const int maxn = 30;
int N, K, X, max_sum_square = -1, nums[maxn];
//temp存放当前方案，ans存放当前平方和最大的方案
vector<int> temp, ans;
//DFS参数设置：index记录当前处理的数据编号，nowK记录当前已经选择了的数据个数，sum和sumSquare分别记录当前数据之和与平方和
void DFS(int index, int nowK, int sum, int sumSquare) {
	//"死胡同"--递归出口
	//注意以下两个if顺序不能颠倒，因为index==N前应该更新数据
	if (nowK == K && sum == X) {
		if (sumSquare > max_sum_square) {
			max_sum_square = sumSquare; //更新最大平方和
			ans = temp; //更新存放当前平方和最大的方案
		}
		return;
	}
	if (index == N || nowK > K || sum > X) return;
	//"岔路口"--选or不选
	//选择index处的数据
	temp.push_back(nums[index]); //选择了
	DFS(index + 1, nowK + 1, sum + nums[index], sumSquare + nums[index] * nums[index]);
	//不选index处的数据
	temp.pop_back(); //消除上面代码“选择了”的影响，重新来到对index处的数据是否选择的岔路口
	DFS(index + 1, nowK, sum, sumSquare); //不选择
}
int main() {
	cin >> N >> K >> X;
	for (int i = 0; i < N; i++)
		cin >> nums[i];
	DFS(0, 0, 0, 0);
	cout << "最大平方和为：";
	cout << max_sum_square << endl;
	cout << "选择方案为：";
	for (auto i = ans.begin(); i < ans.end(); i++)
		cout << *i << " ";
	cout << endl;
	return 0;
}

3.从N个数中选择K个数(每个数可以被选多次)

在问题2，每个数只能被选1次的基础上稍微修改题目为每个数可以被修改多次

【分析】：由于每个数可以被选多次，那么当选择了index处的数据之后，不应该直接进入对index+1的处理，而应该继续选择index，直到遇到“死胡同”–比如已经选了k个数等等，因此，只需要将以上问题2的 DFS(index + 1, nowK + 1, sum + nums[index], sumSquare + nums[index] * nums[index]); 改为 DFS(index, nowK + 1, sum + nums[index], sumSquare + nums[index] * nums[index]);

#include
#include
using namespace std;
const int maxn = 30;
int N, K, X, max_sum_square = -1, nums[maxn];
//temp存放当前方案，ans存放当前平方和最大的方案
vector<int> temp, ans;
//DFS参数设置：index记录当前处理的数据编号，nowK记录当前已经选择了的数据个数，sum和sumSquare分别记录当前数据之和与平方和
void DFS(int index, int nowK, int sum, int sumSquare) {
	//"死胡同"--递归出口
	//注意以下两个if顺序不能颠倒，因为index==N前应该更新数据
	if (nowK == K && sum == X) {
		if (sumSquare > max_sum_square) {
			max_sum_square = sumSquare; //更新最大平方和
			ans = temp; //更新存放当前平方和最大的方案
		}
		return;
	}
	if (index == N || nowK > K || sum > X) return;
	//"岔路口"--选or不选
	//选择index处的数据
	temp.push_back(nums[index]); //选择了
	DFS(index, nowK + 1, sum + nums[index], sumSquare + nums[index] * nums[index]);
	//不选index处的数据
	temp.pop_back(); //消除上面代码“选择了”的影响，重新来到对index处的数据是否选择的岔路口
	DFS(index + 1, nowK, sum, sumSquare); //不选择
}
int main() {
	cin >> N >> K >> X;
	for (int i = 0; i < N; i++)
		cin >> nums[i];
	DFS(0, 0, 0, 0);
	cout << "最大平方和为：";
	cout << max_sum_square << endl;
	cout << "选择方案为：";
	for (auto i = ans.begin(); i < ans.end(); i++)
		cout << *i << " ";
	cout << endl;
	return 0;
}