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
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 100;
int r[MAX];
int p[MAX];
void cutRod(int r[], int n) {
int i, j;
p[1] = r[1];
for (i = 2; i <= n; ++i) {
p[i] = r[i];
for (j = 1; j < i; ++j) {
p[i] = max(p[i], p[i - j] + p[j]);
}
}

}
int main() {
int n;
while (cin >> n) {
for (int i = 1; i <= n; ++i) {
cin >> r[i];
}
int K;
cin >> K;
cutRod(r, K);
cout << p[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
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 100;
int r[MAX];
int p[MAX];
int cutRod(int r[], int k) {
//备忘录
if (p[k] != -1) {
return p[k];
}
if (k == 1) {
p[k] = r[k];
return p[k];
}
else {
p[k] = r[k];
for (int i = 1; i < k; ++i) {
p[k] = max(p[k], p[i] + cutRod(r,k - i));
}
}


}
int main() {
int n;
while (cin >> n) {
for (int i = 1; i <= n; ++i) {
p[i] = -1;
cin >> r[i];
}
int K;
cin >> K;
cutRod(r, K);
for (int i = 1; i <= K; ++i) {
cout << p[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
//钢条切割
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 100;
int r[MAX];
int p[MAX];
int s[MAX];
int cutRod(int r[], int k) {
if (p[k] != -1) {
return p[k];
}
if (k == 1) {
p[k] = r[k];
return p[k];
}
else {
p[k] = r[k];
for (int i = 1; i < k; ++i) {
if (p[k] < cutRod(r, k - i)+p[i]) {
p[k] = p[i] + cutRod(r, k - i);
s[k] = i;
}

}
}
}
int main() {
int n;
while (cin >> n) {
for (int i = 1; i <= n; ++i) {
s[i] = 0;
p[i] = -1;
cin >> r[i];
}
int K;
cin >> K;
cutRod(r, K);
cout << p[K] << endl;
cout << s[K] <<" , "<< K - s[K] << endl;
for (int i = 1; i <= K; ++i) {
cout << p[i] << " ";
cout << s[i] << " , " << i - s[i] << endl;
}
cout << endl;
}
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
//最大字段和
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> a;
int MaxLenSeq(int *T,int n) {
int maxLen;
if (n == 0){
a.push_back(T[n]);
return T[n];
}
maxLen = MaxLenSeq(T, n - 1);
maxLen = max(maxLen+ T[n], T[n]);
a.push_back(maxLen);
return maxLen;
}
int main() {
int T[] = { -2,11,-4,13,-5,-2};
int maxLen=MaxLenSeq(T, 5);
auto max = max_element(a.begin(), a.end());
cout << * max << endl;
cout << a.size() << endl;
for (vector<int>::iterator iter = a.begin(); iter != a.end(); iter++){
cout << (*iter)<< endl;
}
return 0;
}

迭代实现

1
2


数字三角形

递归求解,时间复杂度为 $O(2^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
#include<iostream>
#include<algorithm>
#include<random>
using namespace std;
const int MAX = 101;
int D[MAX][MAX];
int n;
int MaxSum(int i, int j) {
if (n == i)
return D[i][j];
int x = MaxSum(i + 1, j);
int y = MaxSum(i + 1, j + 1);
return max(x, y) + D[i][j];
}
int main() {
cin >> n;
random_device rd;
uniform_int_distribution<unsigned> u(0, 9);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
D[i][j] = u(rd);
cout << D[i][j] << " ";
}
cout << endl;
}
cout << MaxSum(1, 1);
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
//数字三角形 备忘录+分治
#include<iostream>
#include<algorithm>
#include<random>
using namespace std;
const int MAX = 101;
int D[MAX][MAX];
int maxsum[MAX][MAX];
int n;
int MaxSum(int i, int j) {
if (maxsum[i][j] != -1) {
return maxsum[i][j];
}
if (n == i)
maxsum[i][j] = D[i][j];
else {
int x = MaxSum(i + 1, j);
int y = MaxSum(i + 1, j + 1);
maxsum[i][j] = max(x, y) + D[i][j];
}
return maxsum[i][j];
}
int main() {
cin >> n;
random_device rd;
uniform_int_distribution<unsigned> u(0, 9);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
D[i][j] = u(rd);
cout << D[i][j] << " ";
maxsum[i][j] = -1;
}
cout << endl;
}

cout << MaxSum(1, 1);
return 0;
}

迭代实现

1
2


迭代+滚动数组

1
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
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 100;
int maxlen[MAX];
void MaxLen(int a[],int n) {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (a[i] > a[j]) {
maxlen[i] = max(maxlen[j] + 1, maxlen[i]);
}
}
}
}

int main() {
int n;
cin >> n;
int a[] = { 1,7,3,5,9,4,8,9,10,11};
for (int i = 0; i <= n; ++i) {
maxlen[i] = 1;
}
MaxLen(a, n);
cout << *max_element(maxlen, maxlen + n + 1) << endl;
return 0;
}

递归实现

1
2


最长公共子序列(LCS)

迭代实现

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>
#include<cstdlib>
using namespace std;
const int MAX = 100;
char str1[MAX];
char str2[MAX];
int c[MAX][MAX];
int main() {
while (cin >> str1 >> str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
int i, j;
for (i = 0; i <= len1; ++i) {
c[i][0] = 0;
}
for (j = 0; j <= len2; ++j) {
c[0][j] = 0;
}
for (i = 1; i <= len1; ++i) {
for (j = 1; j <= len2; ++j) {
if (str1[i - 1] == str2[j - 1])
c[i][j] = c[i - 1][j - 1] + 1;
else
c[i][j] = max(c[i][j - 1], c[i - 1][j]);
}
}
cout << c[len1][len2] <<endl;
}

return 0;
}

递归实现

1
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 101;
const int INF = 999999;
int m[MAX][MAX];
int s[MAX][MAX];
void matrix_chain_multipy(int p[],int n) {
for (int i = 1; i <= n; ++i) {
m[i][i] = 0;
}
//表示矩阵链A[i]A[i+1]...A[j]的长度,采用自底向上的方法
for (int l = 2; l <= n; ++l) {
//i表示A[i]A[i+1]....A[j]的(开始位置
for (int i = 1; i <= n - l + 1; ++i) {
//j表示A[i]A[i+1]....A[j]的)结束位置
int j = i + l - 1;
m[i][j] = INF;
//用来对A[i]A[i+1]....A[j]在位置k处分割
for (int k = i; k <= j - 1;++k) {
int q = m[i][k] + m[k + 1][j] + p[i - 1]*p[k]*p[j];
if (q < m[i][j]) {
m[i][j] = q;
s[i][j] = k;
}
}
}
}
}
void print_optimal_parens(int s[][MAX],int i, int j) {
if (i == j) {
cout <<"A"<<i;
}
else {
cout << "(";
print_optimal_parens(s, i, s[i][j]);
print_optimal_parens(s, s[i][j] + 1, j);
cout << ")";
}
}
int main() {
int p[MAX];
int len;
while (cin >> len) {
for (int i = 0; i < len; ++i) {
cin >> p[i];
}
matrix_chain_multipy(p, len-1);
int i, j;
cout << m[1][6] << endl;
print_optimal_parens(s, 1, 6);
}
return 0;
}

递归+备忘录

1
2


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
#include<iostream>
#include<algorithm>
using namespace std;
const int NMax = 100;
const int WMax = 3000;
const int VMax = 100;
int m[NMax][WMax];
int values[NMax];
int weight[NMax];
int main() {
int N, W;
while (cin >> N >> W) {
for (int n = 1; n <= N; ++n) {
cin >> weight[n] >> values[n];
}
for (int n = 0; n <= N; ++n) {
m[n][0] = 0;
}
for (int w = 0; w <= W; ++w) {
m[0][w] = 0;
}
for (int n = 1; n <= N; ++n) {
for (int w = 1; w <= W; ++w) {
if (weight[n] > w) {
m[n][w] = m[n - 1][w];
}
else {
m[n][w] = max(m[n - 1][w], m[n - 1][w - weight[n]] + values[n]);
}
}
}
cout << m[N][W] << 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
//0-1背包
#include<iostream>
#include<algorithm>
using namespace std;
const int Nmax = 3500;
const int Wmax = 13000;
int weight[Nmax];
int values[Nmax];
//滚动数组
int m[Wmax];
int main() {
int N, W;//N表示物体个数,W表示背包容量
while (cin >> N >> W) {
for (int n = 1; n <= N; ++n) {
cin >> weight[n] >> values[n];
}
for (int n = 0; n <= W; ++n) {
m[n] = 0;
}
for (int n = 1; n <= N; ++n) {
for (int w = W; w >= 1; --w) {
if(w-weight[n]>= 0)
m[w] = max(m[w], m[w - weight[n]] + values[n]);
}
}
cout << m[W] << endl;
}
}

构造0-1背包最优解

1
2


最优二分搜索树

1
2