【算法】算法设计与分析 期末复习总结

第一章 算法概述

• 时间复杂度比大小，用代入法，代入2即可。
• 求渐进表达式，就是求极限，以极限为O的括号；
• O是指上界，Ω是指下界，θ是指上下界相等，在这里，可以这样理解：

1. f(n) = O(g(n)) 意味着 g(n) 在 n 趋近于无穷大时比 f(n) 大；
2. f(n) = Ω(g(n)) 意味着 g(n) 在 n 趋近于无穷大时比 f(n) 小；
3. f(n) = θ(g(n)) 意味着 g(n) 在 n 趋近于无穷大时和 f(n) 同阶；

第二章 递归与分治

主定理要掌握，选择题必考：

填空有一道二分搜索，掌握简单版和改进版即可：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n, m, a[N], x;

int bisearch(int x, int a[], int left, int right) {
    if (left > right)
        return -1;
    int middle = (left + right) / 2;
    if (a[middle] == x)
        return middle;
    else if (a[middle] < x)
        return bisearch(x, a, left, middle - 1);
    else
        return bisearch(x, a, middle + 1, right);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    while (m--) {
        cin >> x;
        cout << bisearch(x, a, 0, n - 1) <<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n, m, a[N], x;

pair<int, int> bs(int x, int a[], int left, int right) {
	if (left > right) {
		pair<int, int> p(right, left);
		return p;
	}
	int middle = (left + right) / 2;
	if (a[middle] == x) {
		pair<int, int> p(middle, middle);
		return p;
	}
	else if (a[middle] < x)
		return bs(x, a, middle + 1, right);
	else
		return bs(x, a, left, middle - 1);
} 

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	while (m--) {
		cin >> x;
		pair<int, int> p = bs(x, a, 0, n - 1);
		cout << p.first << " " << p.second << endl;
	}
	return 0;
}

接着是排序，快速排序和归并排序的平均时间复杂度都为O(n logn)，快排在最坏情况下的时间复杂度是O(n^2)。

知道中位数概念，一组个数为n的数中，当下标k = (n + 1) / 2时，称为找中位数。

归并的趟数是 logn ，归并的复杂度是 O(n logn)。

第三章 动态规划

两个特征，最优子结构和重叠子问题，后者是动态规划和分治法的区别，分治法的子问题是相互独立的，而动态规划的子问题是有重叠的。

0-1背包问题

题目

给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100)，价值为vi(vi<=100)，背包的容量为C(C<=1000)。
应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。

输入格式:

共有n+1行输入：
第一行为n值和c值，表示n件物品和背包容量c；
接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。

输出格式:

输出装入背包中物品的最大总价值。

输入样例:

在这里给出一组输入。例如：

5 10
2 6
2 3
6 5
5 4
4 6

输出样例:

在这里给出相应的输出。例如：

15

思路

假如现在有五个物品要选，这五个按顺序排下来，从第一个到第五个的最佳选择方案，相当于下面两种的择优选择：

1. 不选第一个+后四个的最佳选择方案；
2. 选第一个+后四个的最佳选择方案；

所以我们发现这是一个具有最优子结构性质的题目，同时也有重合子问题，于是我们可以用动态规划的方法来做。

作为动态规划，我们要严格按照三步走的格式来做：

首先，状态表示，我们设置一个二维数组m[i][j]，作为从第i个到最后一个的最佳选择，同时剩余容量为j；

接着，递归方程，m[i][j] = max ( m[i + 1][j] , m[i + 1][j - w[i]] + v[i] )，也就是从不加第i个的，和加了第i个的这两个方案里选一个总价值最大的；

最后，边界条件，当我们的i为最后一个时，也就是i = n，此时容量从0到最大都可以进行赋值，也就是m[n][j] 的赋值，如果最后一个的重量不比c大，那就设置为这个的价值，如果比c小，就设置为0，注意边界条件在填表时要先写。

现在我们来研究一下最佳方案要怎么打印出来，也就是输出最佳选择组合的各个物品的下标。此时因为dp表已经填完了，所以可以让i从最小开始，我们依次判断即可，怎么判断呢？

直接看物品重量是否不超过剩余重量即可，剩余重量要另起一个变量remain，外层是物品的循环，里面第一重判断是有没有超重，第二重判断是加这个物品是不是比没加要好，把上面max里面的两个照抄即可。

都满足条件，就打印出这个物品的下标，然后使得remain减去这个物品的重量。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 100;

int n, c;
int w[N], v[N];
int m[N][N];

void dp() {
	for (int j = 0; j <= c; j++) {
		if (j >= w[n])
			m[n][j] = v[n];
		else
			m[n][j] = 0;
	}
	
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j <= c; j++) {
			if (j >= w[i])
				m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
			else
				m[i][j] = m[i + 1][j];
		}
	}
	cout << m[1][c];
}

void print() {
	int remain = c;
	for (int i = 1; i <= n; i++) {
		if (remain >= w[i]) {
			if (m[i + 1][remain] < m[i + 1][remain - w[i]] + v[i]) {
				cout << i << ' ';
				remain -= w[i];
			}
		}
	}
	cout << endl;
}

int main() {
	cin >> n >> c;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];
	dp();
	print();
	return 0;
} 

第四章 贪心算法

选择当前看来最好的方案，这个的题目实在太简单了，不写思路。

题目

有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。

输入格式:

共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

输出格式:

输出为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

输入样例:

10
56 12 1 99 1000 234 33 55 99 812

输出样例:

291.90

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int n;
int t[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i];
	sort(t + 1, t + n + 1);
	int total = 0;
	int wait = t[1];
	for (int i = 2; i <= n; i++) {
		total += wait;
		wait += t[i];
	}
	cout << fixed << setprecision(2) << 1.0 * total / n;
	return 0;
}

第五章 回溯法

子集和问题

题目

设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法，并输出利用回溯法在搜索树（按输入顺序建立）中找到的第一个解。

输入格式:

输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。
是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。

输出格式:

输出利用回溯法找到的第一个解，以空格分隔，最后一个输出的后面有空格。当问题无解时，输出“No Solution!”。

输入样例:

在这里给出一组输入。例如：

5 10
2 2 6 5 4

输出样例:

在这里给出相应的输出。例如：

2 2 6

思路

这道题是在一堆数里面选择出一组加起来等于目标数的，用回溯法来做就是画出一棵二叉树，每一层树枝代表一个数字，如果选了这个数字，就顺着左子树往下走，没选就顺着右子树往下走，直到最底下，每次选择与否都要记录下来，还得记录当前的数字之和，如果走到叶子时数字之和等于目标数，就可以输出这组数了。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1000;

int n, c; // 数字个数，目标数 
int a[N], x[N]; //保存数字的数组，表示数字被选与否状态的数组
int sum = 0, remain = 0; //当前已选数字之和，当前剩余数字之和

void backtrack(int t) {
	if (t > n) {
		if (sum == c) {
			for (int i = 1; i <= n; i++) {
				if (x[i] == 1) 
				    cout << a[i] << " ";
			}
			cout << endl;
			exit(0);
		}
		return;
	}
	
	remain -= a[t];
	if (sum + a[t] <= c) {
		x[t] = 1;
		sum += a[t];
		backtrack(t + 1);
		sum -= a[t];
	}
	if (sum + remain >= c) {
		x[t] = 0;
		backtrack(t + 1);
	}
	remain += a[t];
} 

int main() {
	cin >> n >> c;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		remain += a[i];
	}
	backtrack(1);
	cout << "No Solution!" << endl;
	return 0;
}

第六章 分支限界法

分支限界法和回溯法的区别：

回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数达到极大或极小的解，即在某种意义下的最优解；

回溯法以深度优先的方式搜索解空间，分支限界法则以广度优先或以最小耗费优先的方式搜索解空间，分支限界法的搜索策略是，在扩展结点处，先生成其所有子结点，再从当前的活结点表中选择下一个扩展结点。

6.1 分支限界法的基本思想

分支限界法与回溯法的主要区别在于它们对当前扩展结点所采用的扩展方式不同。

搜索方式是广度优先或最小耗费（最大效益）优先。

1. 队列式（FIFO）分支限界法

按队列的先进先出原则选取下一个结点为当前扩展结点。

2. 优先队列式分支限界法

按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前的扩展结点。