五、电路布线
在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱与下端接线柱相连，如图所示。其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任何1≤i<j≤n，第i条连线和第j条连线相交的充分且必要的条件是π(i)>π(j)。
电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。
记
N(i,j)的最大不相交子集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。
(1)当i=1时，
(2)当i>1时，
若j<π(i)。此时，
故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。
2.2 j≥π(i)，(i,π(i))∈MNS(i,j) 。 则对任意(t,π(t)) ∈MNS(i,j)有t<i且π(t)<π(i)。在这种情况下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。
若
则对任意(t,π(t)) ∈MNS(i,j)有t<i。从而
因此，Size(i,j)≤Size(i-1,j)。
另一方面，
故又有Size(i,j)≥Size(i-1,j)，从而Size(i,j)=Size(i-1,j)。
5.1 代码
void MNS(int C[],int n){ int i,j; for(j=0;j<C[1];j++){ size[1][j]=0; } for(j=C[1];j<=n;j++){ size[1][j]=1; } for(i=2;i<n;i++){ for(j=0;j<C[i];j++){ size[i][j]=size[i-1][j]; } for(j=C[i];j<=n;j++){ size[i][j]=size[i-1][j]>(size[i-1][C[i]-1]+1)?size[i-1][j]:(size[i-1][C[i]-1]+1); } } size[n][n]=size[n-1][n]>(size[n-1][C[n]-1]+1)?size[n-1][n]:(size[n-1][C[n]-1]+1); }
void Traceback(int C[],int n,int NET[]){ int i,j=n; int m=0; for(i=n;i>1;i--){ if(size[i][j]!=size[i-1][j]){ NET[m++]=i; j=C[i]-1; } if(j>=C[1]) NET[m++]=1; } }
六、流水作业调度
n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。
流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。
分析：
直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。
设全部作业的集合为N={1，2，…，n}。S⊆N是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。
设π是所给n个流水作业的一个最优调度，它所需的加工时间为 aπ(1)+T’。其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的时间。
记S=N-{π(1)}，则有T’=T(S,bπ(1))。
证明：事实上，由T的定义知T’≤T(S,bπ(1))。若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。则π(1)， π’(2)，…， π’(n)是N的一个调度，且该调度所需的时间为aπ(1)+T(S,bπ(1))<aπ(1)+T’。这与π是N的最优调度矛盾。故T’≤T(S,bπ(1))。从而T’=T(S,bπ(1))。这就证明了流水作业调度问题具有最优子结构的性质。
由 流水作业调度问题的最优子结构性质 可知，
七、投资问题
问题：m元钱，n项投资，fi(x)：将x元投入第i个项目的效益。求使得总效益最大的投资方案。
建模：问题的解是向量<x1,x2,…xn>，xi是投给项目i的钱数，i=1,2,…,n
目标函数max{f1(x1)+f2(x2)+…+fn(xn)}。
约束条件x1+x2+…+xn=m，xi∈N。
7.1 实例
5万元钱，4个项目，效益函数如下表所示
7.2 子问题界定和计算顺序
子问题界定：由参数k和x界定。
k:考虑对项目1,2,…,k的投资
x:投资总钱数不超过x
原始输入：k=n,x=m
子问题计算顺序：
k=1,2,…,n
对于给定的k,x=1,2,…,m
7.3 优化函数的递推方程
Fk(x):x元钱投给前k个项目的最大效益。
多步判断：若知道p元钱（p<=x）投给前k-1个项目的最大效益Fk-1§，确定x元钱投给前k个项目的方案。
递推方程和边界条件：
Fk(x)=max{fk(xk)+Fk-1(x-xk)} k>1。
F1(x)=f1(x)。
7.5 k=1时实例的计算
F1(1)=11。
F1(2)=12。
F1(3)=13。
F1(4)=14。
F1(5)=15。
7.6 k=2时的实例计算
方案(其它,项目2):(0,1),(1,0)
F2(1)=max{f2(1),f1(1)}=11
方案:(0,2),(1,1),(2,0)
F2(2)=max{f2(2),F1(1)+f2(1),F1(2)}=12
方案:(0,3),(1,2),(2,1),(3,0)
F2(3)=max{f2(3),F1(1)+f2(2), F1(2)+f2(1), F1(3)}=16
类似的计算
F2(4)=21， F2(5)=26
7.7 备忘录和解
八、0-1背包问题
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
0-1背包问题是一个特殊的整数规划问题。
设所给0-1背包问题的子问题
算法复杂度分析：
从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算法需要Ω(n2n)计算时间。
最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。
