文档介绍：ACM程序设计
动态规划
DP
Dynamic Programming
1汽车装配线的调度问题
2矩阵乘法
3最长公共子序列
2022/7/3
2
动态规划
1描述最优解的结构
2递归定义最优解的值
3按自底向上的ACM程序设计
动态规划
DP
Dynamic Programming
1汽车装配线的调度问题
2矩阵乘法
3最长公共子序列
2022/7/3
2
动态规划
1描述最优解的结构
2递归定义最优解的值
3按自底向上的方式构造一个最优解
4由计算的结果构造一个最优解
2022/7/3
3
装配线的调度问题
a1,1
e1
e2
t1,1
x1
装配线1
装配线2
a1,2
a1,3
a1,4
a1,n-1
a1,n
a2,1
a2,2
a2,3
a2,4
a2,n-1
a2,n
t1,2
t1,3
t1,n-1
t2,1
t2,2
t2,3
t2,n-1
x2
装配站S1,1
装配站S1,2
装配站S1,3
装配站S1,n-1
装配站S1,4
装配站S1,n
装配站S2,1
装配站S2,2
装配站S2,3
装配站S2,n-1
装配站S2,4
装配站S2,n
2022/7/3
4
装配线的调度问题
7
2
4
2
3
装配线1
装配线2
9
3
4
8
4
8
5
6
4
5
7
3
1
4
2
1
2
1
2
装配站S1,1
装配站S1,2
装配站S1,3
装配站S1,5
装配站S1,4
装配站S1,6
装配站S2,1
装配站S2,2
装配站S2,3
装配站S2,n-1
装配站S2,4
装配站S2,n
3
1
35
37
32
30
24
25
24
16
12
20
18
9
2022/7/3
5
装配线的调度问题
a1,1
e1
e2
t1,1
x1
装配线1
装配线2
a1,2
a1,3
a1,4
a1,n-1
a1,n
a2,1
a2,2
a2,3
a2,4
a2,n-1
a2,n
t1,2
t1,3
t1,n-1
t2,1
t2,2
t2,3
t2,n-1
x2
装配站S1,1
装配站S1,2
装配站S1,3
装配站S1,n-1
装配站S1,4
装配站S1,n
装配站S2,1
装配站S2,2
装配站S2,3
装配站S2,n-1
装配站S2,4
装配站S2,n
f1 1 =e1+a1,1
f1 j =min f1 j-1 +a1,j,f2 j-1 +t2,j-1+a1,j
f2 1 =e2+a2,1
f2 j =min f2 j-1 +a2,j,f1 j-1 +t1,j-1+a2,j
2022/7/3
6
装配线的调度问题
2022/7/3
7
装配线的调度问题
f1 1
e1+a1,1
f1 1
e1+a1,1
For j→2 to n
do if f1 j-1 +a1,j<=f2 j-1 +t2,j-1+a1