算法设计与分析

第一章 绪论

第一章重点的内容是递归问题和一些简单的算法题。

n!问题

示例Python代码:

1
2
3
4
5
6
7
8
def fac(num):
if num == 0 or num == 1:
return 1
else:
return fac(num)*fac(num-1)
if __name__ == "__main__":
ret = fac(5)
print(ret)

自写C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;

int fac(num)
{
if(num==1||num==0)
return 1;
else
return fac(num)*fac(num-1);
}
int main(){
int n;
cin<<n;
int res = fac(n);
cout>>res;
return 0;
}

全排列问题

示例Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def all_permutation(array,start):
if start == len(array):
print(array)
return
for i in range(start,len(array)):
array[start],array[i] = array[i],array[start]
all_permutation(array,start+1)
array[start],array[i] = array[i],array[start]

if _name_ == '_main_':
array=['a','c','b']
all_permutation(array,0)

自写c++代码

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
#include<iostream>
#include<vector>
using namespace std;
void swap(int&a,int&b)
{
int t=a;
a=b;
b=t;
}
void all_permutations(std::vector<int>& array, int start) {
if (start == array.size()) {
for (int num : array) {
std::cout << num << " ";
}
std::cout << std::endl;
return;
}

for (int i = start; i < array.size(); ++i) {
swap(array[start], array[i]);
all_permutations(array, start + 1);
swap(array[start], array[i]); // 恢复原数组
}
}

int main() {
vector<int> array = {1, 2, 3};
all_permutations(array, 0);
return 0;
}

斐波那契数列

示例Python代码

1
2
3
4
5
def Fibonacci(n):
assert n >= 0, "n > 0"
if n <= 1:
return n
return Fibonacci(n-1) + Fibonacci(n-2)

自写c++代码

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int Fibonacci(num){
if(num>0){
if(num==1)
return 1;
else
return Fibonacci(num-1) + Fibonacci(num-2);
}
}

汉诺塔问题

1
2
3
4
5
6
7
def hanoi(n,a,b,c):#n为圆盘数,a代表初始位圆柱,b代表过渡位圆柱,c代表目标位圆柱
if n==1:
print(a,'-->',c)
else:
hanoi(n-1,a,c,b)#将a柱的n-1个圆盘借助c柱移动到b柱
print(a,'-->',c) #将a柱剩下的1个圆盘移动到c柱
hanoi(n-1,b,a,c) #将b柱的n-1个圆盘借助a柱移动到c柱

杨辉三角问题

1
2
3
4
5
6
7
8
9
10
11
def yang(i,j):
if j==0 or j==i:
return 1
else:
return yang(i-1,j)+yang(i-1,j-1)

def print_yang_triangle(n):
for i in range(n):
for j in range(i + 1):
print(yang(i, j), end=" ")
print()

N个连续自然数的连加和问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#依次累加求和
#算法1:
def sum1(a,n):
sum11 = 0
for i in range(a,a+n):
sum11 = sum11 + i
return sum11
#算法2:
def sum2(a1,n):
summ=a1
start=a1+1
end=a1+n-1
for i in range(start,end+1):
summ=summ+i
return summ
#利用等差数列求和公式
def sum3(a1,n):
end=a1+n-1
return (a1+end)*n//2
if __name__ == "__main__":
print ("sum1=",sum1(1,10))
print("sum2=",sum2(1,11))
print("sum3=",sum3(1,10))

调度问题

有n个客户带来n项任务,每项加工时间已知,设为ti(i=1,2,…,n)。从0时刻开始,陆续安排到一台机器上加工。每个任务的完成时间是从0时刻到该任务加工完成的时间。为了使尽可能多的客户满意,我们希望找到总等待时间最少的调度方案,即:总完成时间最短。

1
2
3
4
5
6
7
8
9
10
11
# 将n项任务的加工时间由小到大排序得到的次序为最优调度次序
def schedule(a):
a.sort(key=lambda item:item[1])
return a
if __name__=="__main__":
a=[[1,23],[2,3],[3,20],[4,18],[5,2]]
res = schedule(a)
length = len(res)
print("调度次序为:")
for i in res:
print(i[0])

参考C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>

bool compareSecond(const pair<string, int>& a, const pair<string, int>& b) {
return a.second < b.second;
}

vector<pair<string, int>> schedule(vector<pair<string, int>>& a) {
sort(a.begin(), a.end(), compareSecond);
return a;
}

int main() {
vector<pair<string, int>> events = { {"活动1", 5}, {"活动2", 3}, {"活动3", 8}, {"活动4", 1} };
vector<pair<string, int>> sortedEvents = schedule(events);

for (const auto& event : sortedEvents) {
cout << event.first << ": " << event.second << endl;
}

return 0;
}

最大值问题

1
2
3
4
5
6
7
def arrayMax(a):
n=len(a)
max1=a[0]
for i in range(1,n):
if (a[i]>max1):
max1=a[i]
return max1

在序列A中查找元素K

1
2
3
4
5
6
def find(a,K):
n = len(a)
for i in range(n):
if(a[i]==K):
break
return i

检查序列A和B是否存在公共元素

1
2
3
4
5
6
7
8
def check_common(a_list,b_list):
n_a = len(a_list)
n_b = len(b_list)
for i in range(n_a):
for j in range(n_b):
if a_list[i] == b_list[j]:
return True
return False

第二章 贪心算法

贪心算法本质就是从眼前某一个初始解出发,在每一阶段都做出当前最优的决策,即贪心策略,逐步逼近给定的目标,尽可能快地求得更好的解。贪心算法可以理解为以逐步的局部最优,达到最终的全局最优的方法。

活动安排问题

1
2
3
4
5
6
7
8
9
10
11
void GreedySelector(int n, Type s[],type f[],bool A[]){
A[1] = true;
int j = 1;
for(int i = 2;i <= n;i++){
if(s[i]>=f[j]){
A[i]=true;
j=i;
}
else A[i]=false;
}
}

最优装载问题

1
2
3
4
5
6
7
8
9
void Loading(int x[],Type w[],Type c,int n){
for(int i=1;i<=n;i++){
x[i]=0;
}
for(int i=1;i<=n&&w[i]<=c;i++){
x[i]=1;
c-=w[i];
}
}

单源最短路径问题

dijkstra

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
#线性时间找最小
def dijkstra(start_point, graph):
n = len(graph)
# 初始化各项数据,把dist[start]初始化为0,其他为无穷大
dist = [99999999 for _ in range(n)]#路径长度
pre = [-1 for _ in range(n)]#前驱pre
s = [False for _ in range(n)]#集合S
dist[start_point]=0
for i in range(n):
minLength = 99999999
minVertex = -1
for j in range(n):
if not s[j] and dist[j] < minLength:
minLength = dist[j]
minVertex = j
s[minVertex] = True

# 从这个顶点出发,遍历与它相邻的顶点的边,计算特殊路径长度,更新dist和pre
for edge in graph[minVertex]:
if not s[edge[0]] and minLength + edge[1] < dist[edge[0]]:
dist[edge[0]] = minLength + edge[1]
pre[edge[0]] = minVertex
for e in graph:
print(e)
return dist, pre
if __name__ == "__main__":
data = [
[1, 0, 8],
[1, 2, 5],
[1, 3, 10],
[1, 6, 9],
[2, 0, 1],
[0, 6, 2],
[3, 6, 5],
[3, 4, 8],
[0, 5, 4],
[5, 6, 7],
[5, 3, 8],
[5, 4, 5]]#边集合(顶点,顶点,边权)
n = 7#图的顶点数n
graph = [[] for _ in range(n)]#图的邻接表
#根据输入的图构建图的邻接表
for edge in data:
graph[edge[0]].append([edge[1], edge[2]])
graph[edge[1]].append([edge[0], edge[2]])
dist,pre = dijkstra(1,graph)
print("dist=\n",dist)
print("pre=\n",pre)

哈夫曼编码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
'''
huffman编码
'''
import copy

class Node:
def __init__(self, name, weight):
self.name = name #节点名
self.weight = weight #节点权重
self.left = None #节点左孩子
self.right = None #节点右孩子
self.father = None # 节点父节点
#判断是否是左孩子
def is_left_child(self):
return self.father.left == self

#创建最初的叶子节点
def create_prim_nodes(data_set, labels):
if(len(data_set) != len(labels)):
raise Exception('数据和标签不匹配!')
nodes = []
for i in range(len(labels)):
nodes.append( Node(labels[i],data_set[i]) )
return nodes


# 创建huffman树
def create_HF_tree(nodes):
#此处注意,copy()属于浅拷贝,只拷贝最外层元素,内层嵌套元素则通过引用,而不是独立分配内存
tree_nodes = nodes.copy()
#tree_nodes.sort(key=lambda node: node.weight)#升序排列
while len(tree_nodes) > 1: #只剩根节点时,退出循环
tree_nodes.sort(key=lambda node: node.weight)#升序排列
new_left = tree_nodes.pop(0)
new_right = tree_nodes.pop(0)
new_node = Node(None, (new_left.weight + new_right.weight))
new_node.left = new_left
new_node.right = new_right
new_left.father = new_right.father = new_node
tree_nodes.append(new_node)
tree_nodes[0].father = None #根节点父亲为None
return tree_nodes[0] #返回根节点

#获取huffman编码
def get_huffman_code(root, nodes):
codes = {}
for node in nodes:
code=''
name = node.name
while node.father != None:
if node.is_left_child():
code = '0' + code
else:
code = '1' + code
node = node.father
codes[name] = code
return codes


if __name__ == '__main__':
# labels = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N']
labeks = ['a','b','c','d','e','f']
# data_set = [10,4,2,5,3,4,2,6,4,4,3,7,9,6]
data_set = [9,12,6,3,5,15]
nodes = create_prim_nodes(data_set,labels)#创建初始叶子节点
root = create_HF_tree(nodes)#创建huffman树
codes = get_huffman_code(root, nodes)#获取huffman编码
#打印huffman码
for key in codes.keys():
print(key,': ',codes[key])

最小生成树

Prim算法

每次循环选择一个合适的顶点

时间复杂度 O(n^2)

Kruskal算法

每次循环选择一条合适的边

时间复杂度 O(nlogn)

第三章 分治算法

大整数乘法

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
#通用的两个大整数乘法分治算法
#能够处理两个整数位数不等情况
#能够处理整数位数不能整除的情况(计算之前通过将位数补充到2^n位实现,如整数12345,6789,则会调整为00012345,00006789
from math import log2,ceil
#将给定的整数高位补0,补充够2^n位

def add_zero(str1,real_len,max_len):
add_zero_len = max_len - real_len
return "0" * add_zero_len + str1

def kara(n1,n2):
if n1 < 10 or n2 < 10:
return n1 * n2
n1_str = str(n1)
n2_str = str(n2)
n1_len = len(n1_str)
n2_len = len(n2_str)
real_len = max(n1_len,n2_len)
max_len = 2 ** ceil(log2(real_len))
mid_len = max_len >> 1
n1_add_zero = add_zero(n1_str,real_len,max_len)
n2_add_zero = add_zero(n2_str,real_len,max_len)
a1 = int(n1_add_zero[:mid_len])
a2 = int(n1_add_zero[mid_len:])
b1 = int(n2_add_zero[:mid_len])
b2 = int(n2_add_zero[mid_len:])
u = kara(a1,b1)
v = kara(a1-a2,b2-b1)
w = kara(a2,b2)
return u * 10 ** max_len +(u + v + w) * 10 ** mid_len + w
if __name__ == "__main__":
n1 = 1234
n2 = 5678
res = kara(n1,n2)
print(res)

求最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def n_min(a_list,low,high):
if low >=high:
return a_list[low]
mid = (low + high)//2
left_min = n_min(a_list,low,mid)
right_min = n_min(a_list,mid+1,high)
if left_min < right_min:
return left_min
else:
return right_min
if __name__ == "__main__":
a_list = [8]
res = n_min(a_list,0,0)
print(res)

棋盘覆盖问题

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
def chess(tr,tc,pr,pc,size):#tr,tc:棋盘左上角的位置,即棋盘位置。pr,pc:特殊方格的位置,size为棋盘大小。
global mark
global table
if size==1:
return
mark = mark + 1
count = mark
half=size//2
if pr<tr+half and pc<tc+half:
chess(tr,tc,pr,pc,half)
else:
table[tr+half-1][tc+half-1]=count
chess(tr,tc,tr+half-1,tc+half-1,half)
if pr<tr+half and pc>=tc+half:
chess(tr,tc+half,pr,pc,half)
else:
table[tr+half-1][tc+half]=count
chess(tr,tc+half,tr+half-1,tc+half,half)
if pr>=tr+half and pc<tc+half:
chess(tr+half,tc,pr,pc,half)
else:
table[tr+half][tc+half-1]=count
chess(tr+half,tc,tr+half,tc+half-1,half)
if pr>=tr+half and pc>=tc+half:
chess(tr+half,tc+half,pr,pc,half)
else:
table[tr+half][tc+half]=count
chess(tr+half,tc+half,tr+half,tc+half,half)

if __name__ == "__main__":
mark = 0
n=4
table=[[-1 for x in range(n)] for y in range(n)]
count = chess(0,0,1,1,n)
for i in range(n):
for j in range(n):
print(table[i][j],end=' ')
print('')
print(mark)

幂乘问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def power(a,n):
if a == 1:
return 1
if a == 0:
return 0
if n == 1:
return a
if n % 2 == 0:
b = power(a,n//2)
return b*b
else:
b = power(a,(n-1)//2)
return b * b * a
if __name__ == "__main__":
a = 5
n = 6
k = power(a,n)
print(k)

二分查找

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
#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N = 100010;
int a[N];

int binary_search(int left,int right,int num){
if(left>right)
return -1;
int mid = (1eft+right)/2;
if(num<a[mid]){
return binary_search(left,mid-1,num);
}else if(num>a[mid]){
return binary_search(mid+1,right,num);
}
else{
return mid;
}
}

int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
int num;
cin>>num;
sort(a,a+n);
int mid = binary_search(0,n-1,num);
cout << "list[" << mid << "]=" << a[mid] << endl;
}

选第二大元素

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
def find_max(a_list,left,right):
global dic
if left>=right:
return a_list[left]
mid=(left+right)//2
left_max=find_max(a_list,left,mid)
right_max=find_max(a_list,mid+1,right)
if left_max>right_max:
dic[left_max].append(right_max)
return left_max
else:
dic[right_max].append(left_max)
return right_max

def find_second(n_max):
second_max=n_max[n]
for i in range(1,n):
if n_max[i]>second_max:
second_max = n_max[i]
return second_max

if __name__ == "__main__":
a_list = [6,12,3,7,2,18,90,87,54,23]
n = len(a_list)
dic = {}
for i in range(n):
dic.update([(a_list[i],[])])

first_max = find_max(a_list,0,n-1)
second_max = find_second(dic[first_max])
print(dic)
print(second_max)

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 100010;
int n;

struct List {
int val;
vector<int> out;
}MyList[N];

int find_index(int val) {
for (int i = 0; i < n; i++) {
if (MyList[i].val == val) {
return i;
}
}
return -1;
}

int find_max(int left, int right) {
if (left >= right) {
return MyList[left].val;
}
int mid = (left + right) / 2;
int left_max = find_max(left, mid);
int right_max = find_max(mid + 1, right);
if (left_max > right_max) {
int index = find_index(left_max);
MyList[index].out.push_back(right_max);
return left_max;
}
else {
int index = find_index(right_max);
MyList[index].out.push_back(left_max);
return right_max;
}
}

int find_second(List list) {
int len = list.out.size();
int second_max = list.out[0];
for (int i = 1; i < len; i++) {
if (list.out[i] > second_max) {
second_max = list.out[i];
}
}
return second_max;
}

int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
MyList[i].val = x;
}
int first_max = find_max(0, n - 1);
int second_max = 0;
int t = 0;
for (int i = 0; i < n; i++) {
if (MyList[i].val == first_max) {
t = i;
second_max = find_second(MyList[i]);
break;
}
}
cout << "最大值淘汰的元素:";
for (int i = 0; i < MyList[t].out.size(); i++) {
cout << MyList[t].out[i] << " ";
}
cout << endl;
cout << "第二大元素:" << second_max;
return 0;
}

循环赛日程表

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
#非递归算法
def round_robin_calendar(k):#整数k:比赛人数为2^k。
n = 2**k
import numpy as np
a = np.zeros((n,n))
a[0][0] = a[1][1] = 1
a[1][0] = a[0][1] = 2
for i in range(1,k):
half = 2 ** i
# 左下角的子表中项为左上角子表对应项加2**i
for row in range(half):
for col in range(half):
a[row+half][col]=a[row][col]+half

# 右上角的子表等于左下角子表
for row in range(half):
for col in range(half):
a[row][col+half]=a[row+half][col]

# 右下角的子表等于左上角的子表
for row in range(half):
for col in range(half):
a[row+half][col+half]=a[row][col]
return a

if __name__ =="__main__":
a = round_robin_calendar(4)
print(a)
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
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int n;
const int N = 1000;
int arr[N][N];

void arrange(int p,int q,int n) {
if (n > 1) {
arrange(p, q, n / 2);
arrange(p, q + n / 2, n / 2);
}
for (int i = p + n / 2; i < p + n; i++) {
for (int j = q; j< q + n / 2; j++) {
arr[i][j] = arr[i - n / 2][j + n / 2];
}
}
for (int i = p + n / 2; i < p + n; i++) {
for (int j = q + n / 2; j < q + n; j++) {
arr[i][j] = arr[i - n / 2][j - n / 2];
}
}
}

int main()
{
cin >> n;
memset(arr, 0, sizeof arr);
for (int i = 0; i < n; i++) {
arr[0][i] = i + 1;
}
arrange(0, 0, n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << arr[i][j] << " ";
}
cout << endl;
}
}

归并排序

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
#include<iostream>
suing namespace std;
const int N = 1010;
int q[N];

void merge_sort(int q[],int l,int r){
if(l>=r) return;
int mid = (l+r)>>1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int k = 0;
int i=1,j=mid+1,tmp[N];
while(i<=mid&&j<=r){
if(q[i]<q[j]){
tmp[k++]=q[i++];
}
else{
tmp[k++]=q[j++];
}
}
while(i<=mid){
tmp[k++]=q[i++];
}
while(j<=r){
tmp[k++]=q[j++];
}
for(i=1;j=0;i<=r;i++,j++){
q[i]=tmp[j];
}
}

快速排序

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
#include<iostream>

using namespace std;

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

void quick_sort(int l, int r) {
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[(l + r) / 2];
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort( j + 1, r);
}

int main()
{
cin >> n;
for (int i = 0; i < n; i++) {
cin >> q[i];
}
quick_sort( 0, n - 1);
for (int i = 0; i < n; i++) {
cout << q[i] << " ";
}
return 0;
}

找第K小问题

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
#include<iostream>

using namespace std;

const int N = 1010;
int n,k;
int q[N];

int quickFind(int l,int r,int k){
if(l >= r) return q[l];
int x = q[(l + r) / 2],i = l - 1 , j = r + 1;
while(i < j){
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) swap(q[i],q[j]);
}
int s = j - l + 1;
if(s >= k) return quickFind(l,j,k);
else return quickFind(j+1,r,k-s);
}

int main()
{
scanf("%d%d",&n,&k);
for(int i = 0 ; i < n ; i++)
scanf("%d",&q[i]);

printf("%d",quickFind(0,n-1,k));
return 0;
}

第四章 动态规划

常用场景:

  • 主要用于求解以实践划分阶段的动态过程的优化问题
  • 动态规划算法用于求解具有某种最优性质的问题

动态规划基本思想

  • 经分解得到的各个子问题往往不是相互独立的

  • 在求解过程中,将已解决的子问题的最优值进行保存,在需要时可以轻松取出

动态规划基本要素

  • 最优子结构性质

  • 子问题重叠性质

  • 自底向上的求解方法

矩阵连乘问题

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<vector>
#include <string>

using namespace std;

const int N = 1000;
int m[N][N]; // 记录最优值
int s[N][N]; // 记录最优决策
vector<string> res;

void matrix_chain(vector<int> p,int n) {
for (int i = 0; i < n + 1; i++) {
m[i][i] = 0;
s[i][i] = 0;
}
for (int r = 2; r < n + 1; r++) {
for (int i = 1; i < n - r + 2; i++) {
int j = i + r - 1;
m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
s[i][j] = i;
for (int k = i + 1; k < j; k++) {
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (t < m[i][j]) {
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}

void trace_back(int i, int j, int s[][1000]) {
if (i == j) {
int t = i;
res.push_back("A" + to_string(t));
}else {
res.push_back("(");
trace_back(i,s[i][j],s);
trace_back(s[i][j] + 1, j, s);
res.push_back(")");
}
}

int main()
{
vector<vector<int>> arr = { {3,2},{2,5},{5,10},{10,2},{2,3} };
int n = arr.size();
vector<int> p;
for (int i = 0; i < n; i++) {
if (i == 0) {
p.push_back(arr[0][0]);
p.push_back(arr[0][1]);
}
else {
p.push_back(arr[i][1]);
}
}
matrix_chain(p, n);
trace_back(1, n, s);
for (int i = 0; i < res.size(); i++) {
cout << res[i];
}
return 0;
}

凸多边形最优三角划分

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
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<vector>
#include<string>

using namespace std;

vector<vector<int>> weights = { {0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1} ,{4,3,4,2,1,0} };
const int N = 1000;
int m[N][N], s[N][N];
vector<string> res;
int get_weight(int i, int j, int k,int n) {
if (k < n) {
return weights[i][j] + weights[j][k] + weights[k][i];
}
}

void convex_polygon_optimal(int n) {
memset(m, 0, sizeof m);
memset(s, 0, sizeof s);
for (int i = 0; i < n; i++) {
m[i][i] = 0;
s[i][i] = 0;
}
for (int r = 2; r < n; r++) {
for (int i = 1; i < n - r + 1; i++) {
int j = (i + r - 1) % n;
m[i][j] = m[(i + 1) % n][j] + get_weight(i - 1, i, j, n);
s[i][j] = i;
for (int k = i + 1; k < j; k++) {
int t = m[i][k] + m[(k + 1) % n][j] + get_weight(i - 1, k, j, n);
if (t < m[i][j]) {
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}

void trace_back(int i, int j) {
if (i == j) {
return;
}
else {
trace_back(i, s[i][j]);
trace_back(s[i][j] + 1, j);
res.insert(res.begin(), "v" + to_string((i - 1)) + ",v" + to_string(j) + ",v" + to_string(s[i][j]));
}
}
int main()
{
int n = weights.size();
convex_polygon_optimal(n);
trace_back(1,5);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
return 0;
}

最长公共子序列问题

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
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<vector>
using namespace std;

const int N = 1010;

vector<char> a = { 'z','x','y','x','y','z' };
vector<char> b = { 'x','y','y','z','x' };
int c[N][N],s[N][N];
vector<char> res;

void LCS(int n,int m) {
a.insert(a.begin(), '0');
b.insert(b.begin(), '0');
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < m + 1; j++) {
if (i == 0 || j == 0) {
c[i][j] = 0;
}
else if (a[i] == b[j]) {
c[i][j] = (c[i - 1][j - 1] + 1);
s[i][j] = 0;
}
else if (c[i - 1][j] >= c[i][j - 1]) {
c[i][j] = c[i - 1][j];
s[i][j] = 1;
}
else {
c[i][j] = c[i][j - 1];
s[i][j] = -1;
}
}
}
}

int printLCS(int i,int j) {
if (i == 0 || j == 0) {
return 0;
}
if (s[i][j] == 0) {
printLCS(i - 1, j - 1);
res.push_back(a[i]);
}
else if (s[i][j] == 1) {
printLCS(i - 1, j);
}
else {
printLCS(i, j - 1);
}
}

int main()
{
int n = a.size(), m = b.size();
LCS(n, m);
printLCS(n, m);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
return 0;
}

加工顺序问题

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
49
50
51
52
53
54
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> a = { 3,8,10,12,6,9,15 };
vector<int> b = { 7,2,6,18,3,10,4 };
vector<int> x;
struct Jobtype {
int key, id, N1;
};


bool compare(const Jobtype& a, const Jobtype& b) {
if (a.N1 != b.N1) {
return a.N1 > b.N1;
}
return a.key < b.key;
}


void flow_shop(int n) {
vector<Jobtype> job;
for (int i = 0; i < n; i++) {
x.push_back(0);
}
for (int i = 0; i < n; i++) {
int key = min(a[i], b[i]);
int N1 = a[i] < b[i];
job.push_back({ key,i,N1 });
}
sort(job.begin(),job.end(), compare);
x.resize(n);
int j = 0, k = n - 1;
for (int i = 0; i < n; i++) {
if (job[i].N1) {
x[j++] = job[i].id;
}
else {
x[k--] = job[i].id;
}
}
}

int main()
{
int n = a.size();
flow_shop(n);
cout << "最佳加工次序为:" << endl;
for (int i = 0; i < n; i++) {
cout << x[i] + 1 << " ";
}
}

0-1背包问题

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<iostream>
#include<algorithm>
#include<vector>

using namespace std;
const int N = 1010;

vector<int> v = { 0,2,2,6,5,4 };
vector<int> w = { 0,3,6,5,4,6 };
int dp[N][N];
bool choice[N][N];
bool st[N];
int main() {
int m;
int n = w.size();
cin >> m;
for (int i = 1; i < n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i] && dp[i][j] < dp[i - 1][j - v[i]] + w[i]) {
dp[i][j] = dp[i - 1][j - v[i]] + w[i];
choice[i][j] = true;
}
}
}

cout << "最优值为:" << dp[n - 1][m] << endl;

vector<int> items;
int capacity = m;
for (int i = n - 1; i > 0; i--) {
if (choice[i][capacity]) {
st[i] = true;
capacity -= v[i];
}
}
cout << "背包中所装的物品为:";
for (int i = 1; i < n; i++) {
if (st[i]) {
cout << 1 << " ";
}
else {
cout << 0 << " ";
}
}
return 0;
}

第五章 深度优先搜索

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
#include<iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N],dg[N],udg[N];

void dfs(int u){
if(u == n){
for(int i = 0 ; i < n ; i++)puts(g[i]);
puts("");
return;
}
for(int i = 0 ; i < n ; i ++){
if(!col[i] && !dg[u+i] && !udg[n - u + i]){
g[u][i] = 'Q';
col[i] = dg[u+i] = udg[n-u+i] = true;
dfs(u+1);
col[i] = dg[u+i] = udg[n-u+i] = false;
g[u][i] = '.';
}
}
}
int main()
{
cin >> n;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j ++){
g[i][j] = '.';
}
}
dfs(0);
return 0;
}

0-1背包问题——子集树

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 1010;

vector<vector<int>> goods = { {0,2,6},{1,2,3},{2,6,5},{3,5,4},{4,4,6} };
int bestp = 0; // 当前最优值
int cw = 0; // 当前重量
int cp = 0; // 当前价值
int n = 5; // 问题规模
int c = 10; // 背包容量
int x[N],bestx[N];
bool compare(vector<int>& a, vector<int>& b) {
return a[2] / a[1] > b[2] / b[1];
}

int bound(int i) {
int Wleft = c - cw;
int b = cp;
while (i <= n && goods[i][1] <= Wleft) {
Wleft -= goods[i][1];
b += goods[i][2];
i += 1;
}
if (i <= n) {
b += goods[i][2] / goods[i][1] * Wleft;
}
return b;
}

void backtrack(int t) {
if (t >= n) {
if (bestp < cp) {
bestp = cp;
memcpy(bestx, x, sizeof x);
}
}
else {
if (cw + goods[t][1] <= c) {
x[goods[t][0]] = 1;
cw += goods[t][1];
cp += goods[t][2];
backtrack(t + 1);
cw -= goods[t][1];
cp -= goods[t][2];
}
if (bound(t) > bestp) {
x[goods[t][0]] = 0;
backtrack(t + 1);
}
}
}
int main()
{
sort(goods.begin(), goods.end(), compare);
backtrack(0);
cout << bestp << endl;
for (int i = 0; i < n; i++) {
cout << bestx[i] << " ";
}
}

最大团问题——子集树

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
49
50
51
52
#include<iostream>
#include<vector>

using namespace std;

const int N = 1010;

vector<vector<int>> a = { {0,1,1,0,0},{1,0,1,1,1},{1,1,0,1,1},{0,1,1,0,1},{0,1,1,1,0} };
int bestx[N],x[N];
int bestn = 0 ,cn = 0;
int n;

int place(int t) {
bool ok = true;
for (int j = 0; j < t; j++) {
if (x[j] && a[t][j] == 0) {
ok = false;
break;
}
}
return ok;
}

void backtrack(int t) {
if (t > n) {
memcpy(bestx, x, sizeof x);
bestn = cn;
return;
}
if (place(t - 1)) {
x[t - 1] = 1;
cn += 1;
backtrack(t + 1);
cn -= 1;
}
if (cn + n - t > bestn) {
x[t - 1] = 0;
backtrack(t + 1);
}
}

int main() {
n = a.size();
for (int i = 0; i < n; i++) {
x[i] = i;
}
backtrack(1);
cout << bestn << endl;
for (int i = 0; i < n; i++) {
cout << x[i] << " ";
}
}

批处理作业调度问题——排列树

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
49
50
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 1010;
vector<vector<int>> M = { {0,0,0},{0,2,1},{0,3,1},{0,2,3} };
int f = 0, f1 = 0;
int n;

int f2[N], x[N];
int bestf = INT_MAX;
int bestx[N];

void backtrack(int t) {
if (t >= n) {
std::copy(x, x + n, bestx);
bestf = f;
}
else {
for (int j = t; j < n; j++) {
f1 += M[x[j]][1];
int k = t - 1;
f2[t] = max(f2[k], f1) + M[x[j]][2];
f += f2[t];
if (f < bestf) {
swap(x[t], x[j]);
backtrack(t + 1);
swap(x[t], x[j]);
}
f1 -= M[x[j]][1];
f -= f2[t];
}
}
}

int main()
{
n = M.size();
for (int i = 0; i < n; i++) {
f2[i] = i;
x[i] = i;
}
backtrack(1);
cout << bestf << endl;
for (int i = 0; i < n; i++) {
cout << bestx[i] << " ";
}
}

旅行商问题——排列树

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<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int NoEdge = INT_MAX, N = 1010;

vector<vector<int>> a = { {0,0,0,0,0,0},{0,NoEdge,10,NoEdge,4,12},{0,10,NoEdge,15,8,5},{0,NoEdge,15,NoEdge,7,30},{0,4,8,7,NoEdge,6},{0,12,5,30,6,NoEdge} };
int n;
int x[N], bestx[N];
int bestc = NoEdge;
int cc = 0;

void backtrack(int t) {
int g_n = n - 1;
if (t == g_n) {
if (a[x[g_n - 1]][x[g_n]] != NoEdge && a[x[g_n]][1] != NoEdge && (cc + a[x[g_n - 1]][x[g_n]]) + a[x[g_n]][1] < bestc || bestc == NoEdge) {
std::copy(x, x + n, bestx);
bestc = cc + a[x[g_n - 1]][x[g_n]] + a[x[g_n]][1];
}
}
else {
for (int j = t; j < n; j++) {
if (a[x[t - 1]][x[j]] != NoEdge && (cc + a[x[t - 1]][x[t]]) < bestc || bestc == NoEdge) {
swap(x[t], x[j]);
cc += a[x[t - 1]][x[t]];
backtrack(t + 1);
cc -= a[x[t - 1]][x[t]];
swap(x[t], x[j]);
}
}
}
}

int main()
{
n = a.size();
for (int i = 0; i < n; i++) {
x[i] = i;
}
backtrack(2);
cout << bestc << endl;
for (int i = 0; i < n; i++) {
cout << bestx[i] << " ";
}
return 0;
}

图的m着色问题——满m叉树

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
49
50
51
52
53
#include<iostream>
#include<vector>

using namespace std;

const int N = 1010;

vector<vector<int>> a = { {0,0,0,0,0,0},{0,0,1,1,0,0},{0,1,0,1,1,1},{0,1,1,0,1,0},{0,0,1,1,0,1},{0,0,1,0,1,0 } };
int n;
int m = 3;
int sum1 = 0;
int x[N];
vector<vector<int>> colors;

bool Ok(int k) {
for (int j = 1; j < k; j++) {
if ((a[k][j] == 1) && (x[j] == x[k])) {
return false;
}
}
return true;
}

void backtrack(int t) {
if (t > n) {
sum1 += 1;
vector<int> temp;
for (int i = 0; i < n + 1; i++) {
temp.push_back(x[i]);
}
colors.push_back(temp);
}
else {
for (int i = 1; i < m + 1; i++) {
x[t] = i;
if (Ok(t)) {
backtrack(t + 1);
}
}
}
}

int main()
{
n = a.size() - 1;
backtrack(1);
for (int i = 0; i < colors.size(); i++) {
for (int j = 0; j < colors[i].size(); j++) {
cout << colors[i][j] << ",";
}
cout << endl;
}
}

最小质量机器设计问题——满m叉树

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
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1010;
int COST = 7, n = 3, cw = 0, cc = 0, Total_cost = 0, m = 3, bestw = INT_MAX;
vector<vector<int>> w = { {0,0,0,0},{0,1,2,3},{0,3,2,1},{0,2,3,2} };
vector<vector<int>> c = { {0,0,0,0},{0,1,2,3},{0,5,4,2},{0,3,1,2} };
int bestx[N], x[N];

void backtrack(int t) {
if (t > n) {
Total_cost = cc;
bestw = cw;
std::copy(x, x + n + 1, bestx);
return;
}
for (int j = 1; j < m + 1; j++) {
x[t] = j;
if (cc + c[t][j] <= COST && cw + w[t][j] < bestw) {
cc += c[t][j];
cw += w[t][j];
backtrack(t + 1);
cc -= c[t][j];
cw -= w[t][j];
}
}
}

int main()
{
backtrack(1);
for (int i = 0; i < n + 1; i++) {
cout << bestx[i] << " ";
}
cout << endl;
cout << bestw << endl;
cout << Total_cost << endl;
return 0;
}