抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

动态规划与运筹学

田忌赛马中,使用下等马对战上等马,使用上等马和中等马对战中等马和下等马,这就是运筹学的一个应用

运筹学是应用数学的一个分支,用来解决决策问题,使用数学的方法来做出最佳安排,它在博弈论中也占据着重要地位

动态规划是运筹学的一个分支,是计算最佳决策的过程,它的主要思想是“分解”和“记忆”,分解,即把一个问题分为多个相似的子问题;记忆,即保存已经计算出的结果,防止重复计算

适用条件

最优性原理

若当前问题的决策是最优决策,那么子问题的决策也必须是最优决策

无后效性原理

子问题的决策无法直接影响父问题的决策。无论子问题的决策是否是最佳决策,都不会影响到父问题的决策,但是如果子问题的决策不是最佳决策,那么父问题的决策也一定不是最佳决策

重叠性原理

父问题可以分解成多个子问题,而子问题同样也可以分解成多个子问题,这些子问题可能会出现重复,为了减少计算次数,需要在计算后保存子问题的解,在下次遇到时就可以直接使用

斐波那契数列

问题描述

求出前两项都为1的斐波那契数列的第50项

问题分解

用f(n)来表示第n个斐波那契数,则f(n)=f(n-1)+f(n-2),且当n=1,2时,f(n)=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
#include <iostream>
#include <stdio.h>
#include <string.h>

long long fib[51]{};

long long Fibonacci(int i);

int main(){
//打印第50个斐波那契数
printf("%lld\n", Fibonacci(50));
return 0;
}

//返回第i个斐波那契数列的数
long long Fibonacci(int i){
if(fib[i] != 0) return fib[i];
if(i <= 2){
fib[i] = 1;
} else{
fib[i] = Fibonacci(i-1) + Fibonacci(i-2);
}
return fib[i];
}

数塔问题

问题描述

Description
设有一个三角形的数塔,顶点结点为根结点,每个结点有一个整数数值。从顶点出发,在每一个结点可以选择向左下走或者向右下走,一直走到底层,要求找出一条路径,使得路径上的和最大。
Input
输入数塔层数n
输入n层数塔
Output
输出最大和
Sample Input
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
Sample Output
max=86

问题分解

设第i层,第j个数为a[i][j], 向下走的最大和为f(i, j),则f(i, j)=a[i, j] + max{f(i+1,j),f(i+1,j+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
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int n;
int **arr;//由于不知道n的范围,采用指针方式定义
int **res;//储存已经计算过的结果

int f(int i, int j);

int main() {
cin >> n;//输入层数
arr = new int *[n];
res = new int *[n];
for(int i=0;i<n;i++){
arr[i] = new int [n];
res[i] = new int [n]{};//在定义指针的同时初始化数组为0
}
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
cin >> arr[i][j];//输入数字
}
}
cout << "max=" << f(0,0);
return 0;
}

int f(int i, int j){
if(res[i][j] != 0) return res[i][j];
if(i >= n-1){//已经到达最底层
res[i][j] = arr[i][j];
}else{
res[i][j] = arr[i][j] + max(f(i+1,j),f(i+1,j+1));;
}
return res[i][j];
}

最长公共子序列

问题描述

Description
给定两个字符串,输出两个字符串的最长公共子序列长度
Input
输入2个字符串(保证字符串长度不超过500)
文件有多组数据以‘#’号结束
Output
输出最长公共子序列长度
Sample Input
abc
abc
abcd
acdef
#
Sample Output
3 3

问题分解

设函数f(i,j)返回字符串a的第i个字符开始,字符串b的第j个字符开始的最长公共序列长度。当i==j时,f(i,j)=f(i-1,j-1)+1,否则,f(i,j)=max{f(i,j-1),f(i-1,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
33
34
35
36
37
38
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

char a[501];//序列A
char b[501];//序列B
int len_a,len_b;
int res[501][501];

int f(int i, int j);

int main() {
while (cin >> a && a[0] != '#' && cin >> b) {
//初始化res数组
for (int i = 0; i < 501; i++) {
for (int j = 0; j < 501; j++) {
res[i][j] = -1;
}
}
len_a = strlen(a);
len_b = strlen(b);
cout << f(0,0) << endl;
}
return 0;
}

int f(int i, int j) {
if(i >= len_a || j >= len_b) return 0;
if (res[i][j] != -1) return res[i][j];
if (a[i] == b[j]) {
res[i][j] = f(i + 1, j + 1) + 1;
} else {
res[i][j] = max(f(i + 1, j), f(i, j + 1));
}
return res[i][j];
}

01背包

详见 01背包问题-回溯与动态规划解法

导弹拦截问题

问题描述

Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
Input
输入多个数据m:(m<=30000)
389 207 155 300 299 170 158 65
Output
6(最多能拦截的导弹数)
2(要拦截所有导弹最少要配备的系统数)
Sample Input
389 207 155 300 299 170 158 65
Sample Output
6
2

问题分解

拦截弹一次比一次低,说明每次导弹的高度会越来越低,把拦截的导弹按序号排序,它们的高度会是一个下降序列,所以最多能拦截的导弹数就是最长下降子序列的长度

同理,每次计算出最长下降子序列之后,移除这条子序列,重复计算,所以最少配备的系统数就是下降子序列的数量,显然,下降子序列的数量就是最长上升子序列的长度,因为在上升子序列里,每一项都一定分布在不同的下降序列里

设导弹数量为len, f(i)表示从i开始的最长下降子序列长度,只需要从它后面的导弹里找出导弹j,使得height(i) >= height(j),且f(j)+1>=f(i),则f(i)的值就是f(j)+1

g(i)表示从i开始的最长上升子序列长度,它与f(i)同理,只是要把条件改成height(i) < height(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
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 <stdio.h>
#include <string.h>
#include <sstream>
#include <string>

using namespace std;

int temp;
int height[1000];
int len = 0;

int res_f[1000]{};
int res_g[1000]{};

int f(int i);//最长下降子序列
int g(int i);//最长上升子序列

int max_f = 1, max_g = 1;//记录最大值

int main() {
string s;
getline(cin, s);
istringstream istr(s);
//读取导弹高度
while (istr >> temp) {
height[len] = temp;
len++;
}
//求最大值
for (int i = 0; i < len; i++) {
if (f(i) > max_f) max_f = f(i);
if (g(i) > max_g) max_g = g(i);
}
cout << max_f << endl << max_g << endl;
return 0;
}

int f(int i) {
if (res_f[i] != 0) return res_f[i];
res_f[i] = 1;//因为它自己就是一个序列,所以初始值为最小值为1
if (i < len - 1) {
for (int j = i + 1; j < len; j++) {
if (height[i] >= height[j] && f(j) + 1 >= res_f[i]) res_f[i] = f(j) + 1;
}
}
return res_f[i];
}

int g(int i) {
if (res_g[i] != 0) return res_g[i];
res_g[i] = 1;//因为它自己就是一个序列,所以初始值为最小值为1
if (i < len - 1) {
for (int j = i + 1; j < len; j++) {
if (height[i] < height[j] && g(j) + 1 >= res_g[i]) res_g[i] = g(j) + 1;
}
}
return res_g[i];
}

评论