Czj's Blog

算法设计与分析-第五章

发表于 更新于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

0/1 背包问题（回溯法）

[NOIP 2002 普及组] 选数

[USACO1.5] 八皇后 Checker Challenge

0/1 背包（回溯法）

题目大意

给定一组物品，每个物品都有各自的重量和价值，同时给定一个背包的容量。要求在背包容量的限制下，选择物品装入背包，使得装入背包的物品总价值最大，且每个物品只能选择一次，最后输出这个最大总价值。

解法描述

回溯算法

  1. 算法思想

    回溯算法采用深度优先搜索策略，递归探索所有可能的物品选择组合，遍历解空间树。在搜索过程中，尝试将物品放入或不放入背包，构建可能的解。到达递归边界（考虑完所有物品）时，记录当前组合的总价值并与已记录的最大价值比较，若更大则更新最大价值。不断回溯尝试其他组合，直至找到最优解。

  2. 实现方式

    • 核心函数：dfs函数接收当前物品索引u、背包已装物品总重量sum、总价值val和剩余物品总价值rem。若u > n，比较并更新最大价值ans；若sum > m或rem + val < ans，直接返回。否则，递归考虑放入和不放入当前物品的情况。
    • 主函数流程：在main函数中，读入n、m和物品的重量、价值，计算总重量tmp_w和总价值tmp_v。若tmp_w <= m，直接输出tmp_v；否则调用dfs(1, 0, 0, tmp_v)进行回溯搜索，最后输出最大价值ans。

  3. 复杂度分析

    • 时间复杂度：每个物品有放入或不放入两种选择，对于n个物品，时间复杂度为\(O(2^n)\)，物品数量增加时，运行时间呈指数级增长。
    • 空间复杂度：主要取决于递归调用栈深度，最坏情况下深度为n，空间复杂度为\(O(n)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9;
int n, m, v[N], w[N], tmp_w, tmp_v, ans;
//int f[N];
//int n, m, v[N], w[N], ans, tmp;
//bool st[N];

inline void dfs(int u, int sum, int val, int rem) {
	if (u > n) {
		if (ans < val) {
			ans = val;
			cout << ans << endl;
		}
		return;
	}
	if (sum > m) return ;
	if (rem + val < ans) return;
	dfs(u + 1, sum, val, rem - v[u]);

	dfs(u + 1, sum + w[u], val + v[u], rem - v[u]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		tmp_w += w[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		tmp_v += v[i];
	}
//	for (int i = 1; i <= n; i++) {
//		cout << "质量是" << w[i] << " " << "价值是" << v[i] << endl;
//	}
	if (tmp_w <= m) {
		cout << tmp_v << endl;
		return 0;
	}
	//用dfs来做
	dfs(1, 0, 0, tmp_v);

	cout << ans;
	return 0;
}

[NOIP 2002 普及组] 选数

题目大意

给定一个包含\(n\)个整数的集合，从该集合中选取\(k\)个元素，找出所有满足这\(k\)个元素之和为素数的组合，最后输出满足条件的组合数量。

解法描述

回溯算法

  1. 算法思想

    回溯算法通过深度优先搜索的方式遍历所有可能的组合情况。它从空组合开始，逐步添加元素，在每一步决策中，尝试选择当前未被选择的元素加入组合，直到组合中元素个数达到\(k\)个。然后检查该组合元素之和是否为素数，如果是，则将满足条件的组合数量加 1。通过不断回溯，撤销之前的选择，尝试其他可能的组合，从而找出所有符合条件的组合。

  2. 实现方式

    • 素数判断函数：check(int x)函数用于判断一个数是否为素数。通过从 2 到\(\sqrt{x}\)遍历，如果能找到一个数\(i\)使得\(x\)能被\(i\)整除，则\(x\)为合数，返回 0；否则\(x\)为素数，返回 1。
    • 递归搜索函数：dfs(int u, int sum, int start)是核心递归函数。u表示当前已选择的元素个数，sum表示当前组合的元素之和，start表示从集合中的第start个元素开始考虑选择。当u == k时，说明已选择了\(k\)个元素，调用check(sum)检查当前组合的和是否为素数，若是则ans++，然后返回。否则，从start开始，遍历集合中的元素，对于每个元素，递归调用dfs(u + 1, sum + x[i], i + 1)，即选择该元素加入组合，继续搜索下一个元素。

  3. 复杂度分析

    • 时间复杂度：算法的时间复杂度为\(O(n^k)\)。因为在选择\(k\)个元素的过程中，对于每一个位置的元素选择，都有\(n\)种可能（在选择第一个元素时有\(n\)种选择，选择第二个元素时有\(n - 1\)种选择，但由于从start开始，整体可近似看作每次都有\(n\)种选择的复杂度），所以总的时间复杂度为\(n\)的\(k\)次方。随着\(n\)和\(k\)的增大，算法运行时间会快速增长。
    • 空间复杂度：空间复杂度主要由递归调用栈的深度决定。在最坏情况下，递归深度为\(k\)（即选择\(k\)个元素的过程），所以空间复杂度为\(O(k)\)。此外，代码中还使用了一些辅助变量，如数组x和st，但它们的空间复杂度相对较小，不影响整体空间复杂度的量级。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

/*
  选数本质上是一个组合问题
  因此可以考虑让选取有顺序，避免构建成排列树
 */
int n, k, ans;
const int N = 20;
int x[N];
bool st[N];

bool check(int x) {
	//返回0说明是合数，返回1说明是素数
	for (int i = 2; i <= x / i; i++) {
		if (x % i == 0) return 0;
	}
	return 1;
}

void dfs(int u, int sum, int start) {
	if (u == k) {
		if (check(sum)) {
			ans++;
		}
		return;
	}
	for (int i = start; i < n; i++) {
		dfs(u + 1, sum + x[i], i + 1);
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	dfs(0, 0, 0);
	cout << ans << endl;
	return 0;
}

[USACO1.5] 八皇后 Checker Challenge

题目大意

在一个 \(n\times n\) 的棋盘上放置 \(n\) 个棋子，要求每行、每列有且仅有一个棋子，并且每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。需要找出所有满足条件的棋子放置方案。

解法描述

回溯算法

  1. 算法思想

    回溯算法是一种深度优先搜索策略，用于解决组合优化问题。对于八皇后问题，我们需要在棋盘上逐步尝试放置棋子，每放置一个棋子，都要检查其是否满足题目所规定的约束条件（每行、每列、每条对角线最多一个棋子）。如果满足条件，就继续在后续行放置棋子；如果不满足，就撤销当前放置，尝试其他位置。通过不断地尝试和回溯，遍历所有可能的放置方案，找出满足条件的解。

  2. 实现方式

    • 分解问题：八皇后问题可以分解为逐行放置棋子的子问题。因为每行只能放置一个棋子，所以我们可以按行依次考虑，对于每一行，尝试在不同的列放置棋子。
    • 状态表示：为了判断某一列、某条对角线是否已经有棋子，我们需要合适的数据结构来记录状态。对于列，我们可以用一个一维数组 col 来标记，col[i] 表示第 i 列是否有棋子；对于对角线，由于从左上到右下的对角线可由 i + j 唯一标识，从右上到左下的对角线可由 j - i + n 唯一标识，所以分别用 deg 和 udeg 数组来标记这两类对角线的状态。
    • 约束条件检查：在尝试放置一个棋子时，我们需要检查该位置所在的列、两条对角线是否已经有棋子。如果这些位置都没有棋子，说明该放置是合法的，可以继续递归处理下一行；否则，需要尝试其他列。
    • 回溯机制：当在某一行的所有列都尝试过，或者在某一步发现无法继续放置合法的棋子时，我们需要回溯到上一行，撤销上一行的放置，然后尝试该行的其他列。

  3. 复杂度分析

    • 时间复杂度：在最坏情况下，对于每一行都有 \(n\) 种可能的放置位置，总共需要处理 \(n\) 行，因此时间复杂度为 \(O(n^n)\)。随着 \(n\) 的增大，算法的运行时间会急剧增加。
    • 空间复杂度：主要的空间开销来自递归调用栈和辅助数组。递归调用栈的深度最大为 \(n\)，而辅助数组 col、deg、udeg 和 g 的空间复杂度均为 \(O(n^2)\)，所以总的空间复杂度为 \(O(n^2)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
int n, ans;
const int N = 20;
bool g[N][N], col[N], deg[N], udeg[N];

void  dfs(int u) {
	if (u == n) {
		if (ans < 3) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j <= n; j++) {
					if (g[i][j]) cout << j + 1 << " ";
				}
			}
			cout << endl;
		}
		ans++;

		return ;
	}

	for (int i = 0; i < n; i++) {
		if (!col[i] && !deg[i + u] && !udeg[i - u + n]) {
			col[i] = deg[i + u] = udeg[i - u + n] = 1;
			g[u][i] = 1;
			dfs(u + 1);
			g[u][i] = 0;
			col[i] = deg[i + u] = udeg[i - u + n] = 0;
		}
	}
}

int main() {
	cin >> n;
	dfs(0);

	cout << ans;

	return 0;
}