算法设计与分析之动态规划

一、要点

1. 什么是动态规划算法

动态规划算法与分治法类似,其基本思想是将待求问题分解成若干个子问题,先求子问题,再结合这些子问题的解得到原问题的解,与分治法不同的是,动态规划会将前面求得的子问题的解保存在一个表中,在需要时用到以求得的答案,这样避免了重复的大量计算。

2. 动态规划的步骤

  1. 找出最优解的性质,并刻画其结构特征。
  2. 递归的定义最优值。
  3. 自底向上的方式计算最优值。

  4. 根据计算最优值时得到的信息,构造最优解。

3. 动态规划算法的基本要素

  1. 最优子结构性质:问题的最优解包含子问题的最优解,反过来说,我们可以通过子问题的最优解求出问题的最优解。也可以理解为,后面的状态可以通过前面的状态推到出来。
  2. 重叠子问题性质:不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态

二、习题以及解析

1. 独立任务最优调度问题

题目: 用2台处理机$A$和$B$处理$n$个作业。设第i个作业交给机器A处理时需要时间$a_i$,若由机器B来处理,则需要时间$b_i$。由于各作业的特点和机器的性能关系,很可能对于某些$i$ ,有$a_i\geq b_i$ ,而对于某些$j$ ,$j\neq i$ 有$a_j>b_j$ 。既不能将一个作业分开由两台机器处理,也没有一台机器能同时处理2个作业。设计一个动态规划算法,使得这2台机器处理完这$n$个作业时间最短(从任何一台机器开弓到最后一台机器停工的总时间)。研究一个实例:$(a_1,a_2,a_3,a_4,a_6) = (2,5,7,10,5,2),(b_1,b_2,b_3,b_4,b_5,b_6) = (3,8,4,11,3,4)$。

输入:

1
2
3
6
2 5 7 10 5 2
3 8 4 11 3 4

输出:

1
15

1.题解:利用dp存储每个状态的结果,最后选出最优的一个解。转换方程:$dp[i][j]=min(dp[i-1][j]+b[i],dp[i-1][j-a[i]]);dp[i][j]$代表做完前i个任务,A机器花几分钟情况下,B机器所花的时间,也就是说$dp[i][j]$就是表示B机器所花时间。

$dp[i][j] = dp[i-1][j]+b[i]$代表第i个任务交给B来做,所以做完前i个任务的时候,A机器和前$i - 1$的任务一样,还是花了j分钟,而B机器则花$dp[i-1][j]+b[i]$分钟;

$dp[i][j] = dp[i-1][j-a[i]]$代表第i个任务交给A来做,现在的A机器花费时间是j,所以在前$i - 1$个任务完成的时候,A机器是花了$j-a[i]$分钟的,所以现在B机器还是花了$dp[i-1][j-a[i]]$分钟;

一直到$dp[n][i]$:代表所有的任务都做完了,B机器所花费的时间,那么最迟的时间就是B的时间和A的时间求最大值;

1
2
for(int i=0; i<=sum; i++)
ans=min(ans,max(dp[n][i],i));//max(dp[n][i],i)

表示完成前n个作业A机器花i分钟 B机器花$dp[n][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
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
int a[201], b[201];
int n;
int dp[202][10000];//dp[i][j] 表示前i个作业中A机器花j分钟的时候 B机器所花时间
int main(int argc, char* argv[]) {
cin >> n;
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>b[i];
int sum=0;
for(int i=1; i<=n; i++) {
sum+=a[i];
for(int j=0; j<=sum; j++) {
dp[i][j]=dp[i-1][j]+b[i];//dp[i-1][j]中对a的时间分配已经分配好,无需在判断a,直接添加b[i]的时间。
if(j>=a[i]) dp[i][j]=min(dp[i-1][j]+b[i],dp[i-1][j-a[i]]);//当时间超过当前a[i] 就需要判断是否需要更新
}
}
int ans=999999;
//max(dp[n][i],i) 表示完成前n个作业A机器花i分钟 B机器花dp[n][i]分钟情况下,最迟完工时间,最后一个机器完成才算最终完成。
for(int i=0; i<=sum; i++)ans=min(ans,max(dp[n][i],i));
cout<<ans<<endl;
return 0;
}

2. 最优批处理问题

问题描述: 在一台超级计算机上,编号为1、2、3…、n的n个作业等待批处理,批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业。从时刻0开始,分批加工这些作业。在每批作业开始前,机器需要启动时间S而完成这批作业所需的时间是单独完成批中各个作业需要时间的总和。单独完成第$i$个作业所需要的时间是$t_i$,所需的费用是它的完成时刻乘以一个费用系数$f_i$

题解:

设$z_i$是

输入:

1
2
3
4
5
6
7
5
1
1 3
3 2
4 3
2 3
1 4

输出:

1
153

2.题解

image-20201123112546597

代码:

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;
int z[1000] = {};
int S,n;
int st[1000] = {},sw[1000] = {};
int t[1000] = {},w[1000] = {};
int dyna(){
z[n+1] = 0;
for (int i = n; i; i--) {
//倒序累加
st[i] = st[i+1]+t[i];//
sw[i] = sw[i+1]+w[i];//
z[i] = (st[i]+S)*sw[i];//初始化每一个任务各一个组
}
for (int i = n; i; i--) {
for(int j = i+1;j<=n+1;j++)
z[i] = min(z[i],z[j]+sw[i]*(S+st[i]-st[j]));
}
return z[1];
}
int main(int argc, const char * argv[]) {
cin>>n;
cin>>S;
for (int i = 1; i<=n; i++) {
cin>>t[i];
cin>>w[i];
}
cout<<dyna()<<endl;
}

3. 石子合并问题

问题描述: 在一个圆形操场摆放着$n$堆石子。现将石子有次序的合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。设计一个算法,计算出将n堆石子合并成一堆最小得分和最大得分。

输入:

1
2
4
4 4 5 9

输出:

1
2
43
54

3.题解:

首先,我们对这两个结果进行解释。对于这四堆石子,我们可以先从左到右合并,那它的得分就是:

会发现最小得分是优先合并石子数少的两堆,相反,最大得分就是优先合并石子数多的两堆,也就有:

注意并不是所有测试案例都是有一定顺序的,如 9,4,4,5 的结果与上述一致,因此每一次都需要进行判断相邻两堆相加的值是当前得分最小或最大的。

难点在于把环形当做直线型

4 4 5 9 5 4 4

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 <stdio.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int Arr[300],Sum[300];
int Min[300][300], Max[300][300];//第i到第j堆求和分数。
int main() {
int n;
cin >> n;
// 初始化数组
for (int i = 1; i <= n; i++) {
cin >> Arr[i];
Arr[i + n] = Arr[i];
}

// 计算最大和
for (int i = 1; i <= 2 * n; i++) {
Sum[i] = Sum[i - 1] + Arr[i];
}

// 开始递归循环
for (int i = 2 * n-1; i >= 1; i--) {
for (int j = i + 1; j < i + n; j++) {
Min[i][j] = INF;
for (int k = i; k < j; k++) {
Min[i][j] = min(Min[i][j], Min[i][k] + Min[k + 1][j] + Sum[j] - Sum[i - 1]);
Max[i][j] = max(Max[i][j], Max[i][k] + Max[k + 1][j] + Sum[j] - Sum[i - 1]);
}
}
}

// 遍历找到最大与最小值
int MaxValue = 0, MinValue = INF;
for (int i = 1; i <= n; i++) {
MaxValue = max(MaxValue, Max[i][i + n - 1]);
MinValue = min(MinValue, Min[i][i + n - 1]);
}

cout << MinValue << endl << MaxValue << endl;

}

4. 最小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
#include <iostream>
using namespace std;
int n,m;
int a[100] = {};
int dp[100][100] = {};//i长度 j段数。
int min1,max1,temp;
int solve(){
for (int i = 1; i<=n; i++) {
dp[i][1] = dp[i-1][1] + a[i];
}
for (int i = 1; i<=n; i++) {
for (int j = 2; j<=m; j++) {
min1 = 99999;
for (int k = 1; k<i; k++) {
min1 = min(min1,max(dp[k][j-1],dp[i][1]-dp[k][1]));
}
dp[i][j] = min1;
}
}
return dp[n][m];
}
int main() {
cin>>n>>m;
for (int i = 1; i<=n; i++) cin>>a[i];
cout<<solve()<<endl;
}