关键路径算法c
① pmp如何计算关键路径
pmp计算关键路径的方法如下：
关键路径法（Critical Path Method）是一种用来预测总体项目历时的项目源网络分析技术。所谓“关键路径”，是指当我们完成了项目进计划后，在项目的网络图上，存在着若干条从项目启动到项目结束之间的路径，但是对其中一条（严格的来说，可能存在一条以上）路径上来说。
所谓正推法就是从项目的第一个活动到最后一个活动跟踪全部活动的先后关系，计知算出每个活动的最早开始时间（ES）和最早结束时间（EF）。
所谓倒道推法则是从最后一个活动开始向前追溯到第一个活动，计算出每个活动的最晚开始时间（LS）和最晚结束时间（LF）。
PMP作为项目管理资格认证考试，已在国际上树立了其权威性：
1、PMP为美国培养了一大批项目管理专业人才，项目管理职业已成为美国的“黄金职业”。在中国许多媒体已把PMP称为继MBA，MPA之后的三大金字招牌之一；
2、PMP认证已成为了一个国际性的认证标准，用英语、德语、法语、日语、韩语、西班牙语、葡萄牙语和中文等九种语言进行认证考试；
3、到目前为止，全球有80多万名PMP，中国大陆地区获得“PMP”头衔的已有18万多人，并逐年增长；
4、各国纷纷效仿美国的项目管理认证制度，推动了世界项目管理的发展。
② 什么是关键路径
在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。
求关键路径的算法分析
（1） 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径； （2） 只有缩短关键活动的工期才有可能缩短工期； （3） 若一个关键活动不在所有的关键路径上，减少它并不能减少工期； （4） 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。
探寻关键路径
AOE网
用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网 。AOE网常用于估算工程完成时间。例如： 图1
图1 是一个网。其中有9个事件v1，v2，…，v9；11项活动a1，a2，…，a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如 v1表示整个工程开始，v9 表示整个工程结束。V5表示活动，a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6天时间可以完成。
AOE 网具有的性质
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。 只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。 表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。 2)
最早发生时间和最晚发生时间的定义
可以采取如下步骤求得关键活动： A、从开始顶点 v 1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早发生时间。 Ve(k)=max{ve(j) t(<j,k>)} （ 1.1 ） j ∈ T 其中T是以顶点vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。 如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。 表1
B、从完成顶点 v n 出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间: vl(j)=min{vl(k)-t(<j,k>)} k ∈ S 其中 S 是以顶点vj是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。 C、求每一项活动ai(1 ≤ i ≤ m)的最早开始时间e(i)=ve(j)；最晚开始时间： l(i)=vl(k)-t(<j,k>) 若某条弧满足 e(i)=l(i) ，则它是关键活动。 对于图1所示的 AOE 网，按以上步骤的计算结果见表1，可得到a1 , a4 , a7 , a8 , a10 , a11 是关键活动。
AOE 网的关键路径
图2
这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条，如图7.21的AOE网中有二条关键路径，(v1, v2, v5, v7 , v9 ) 和 (v1 , v2 , v5 , v8 , v9 )它们的路径长度都是16 。如图2所示：
AOE网研究的问题
（1） 完成整个工程至少需要多少时间； （2） 哪些活动是影响工程的关键。 1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。
关键路径的几个术语
（1） 关键路径 从源点到汇点的路径长度最长的路径叫关键路径。 （2） 活动开始的最早时间e(i) （3） 活动开始的最晚时间l(i) 定义e(i)=l(i)的活动叫关键活动。 （4） 事件开始的最早时间ve(i) （5） 事件开始的最晚时间vl(i) 设活动ai由弧<j,k>(即从顶点j到k)表示，其持续时间记为t(<j,k>),则 e(i)=ve(j) l(i)=vl(k)-t(<j,k>) (6_6_1) 求ve(i)和vl(j)分两步： · 从ve(1)=0开始向前递推 ve(j)=Max{ ve(i)+t(<i,j>) } (6_6_2) <i,j>T, 2<=j<=n 其中，T是所有以j为弧头的弧的集合。 · 从vl(n)=ve(n)开始向后递推 vl(i)=Min{ vl(j)-t(<i,j>) } (6_6_3) <i,j>S, 1<=i<=n-1 其中，S是所有以i为弧尾的弧的集合。 两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。 4、 求关键路径的算法 (1) 输入e条弧<j,k>，建立AOE网的存储结构。 (2) 从源点v1出发，令ve(1)=0,求 ve(j) 2<=j<=n。 (3) 从汇点vn出发，令vl(n)=ve(n),求 vl(i) 1<=i<=n-1。 (4) 根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。 求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。 Status ToplogicalSort(ALGraph G,stack &T){ FindInDegree(G,indegree); InitStack(S);count=0; ve[0..G.vexnum-1]=0; while(!StackEmpty(S)) { Pop(S,j);Push(T,j); ++count; for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; if(--indegree[k]==0) Push(S,k); if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info); } } if(count<G.vexnum) return ERROR; else return OK; } status CriticalPath(ALGraph G){ if(!ToplogicalOrder(G,T)) return ERROR; vl[0..G.vexnum-1]=ve[0..G.vexnum-1]; while(!StackEmpty(T)) for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; t=*(p->info); if(vl[k]-t<vl[j]) vl[j]=vl[k]-t; } for(j=0;j<G.vexnum;++j) for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; t=*(p->info); ee=ve[j]; el=vl[k]; tag=(ee==el)?’*’:’’; printf(j,kt,ee,el,tag); } }
③ 给一些程序填空题,PASCAL的
真想要？要有耐心看下去的。。。。
自己挑些题做吧。
2006：
1．（选排列）下面程序的功能是利用递归方法生成从 1 到 n(n<10)的 n 个数中取 k(1<=k<=n)个数的 全部可能的排列（不一定按升序输出）。例如，当 n=3，k=2 时，应该输出（每行输出 5 个排列）：
12 13 21 23 32
31
程序：
Program ex501; Var i,n,k:integer;
a:array[1..10] of integer;
count:longint;
Procere perm2(j:integer);
var i,p,t:integer;
begin
if ① then
begin
for i:=k to n do begin inc(count);
t:=a[k]; a[k]:=a[i]; a[i]:=t;
for ② do write(a[p]:1);
write(' ');
t:=a[k];a[k]:=a[i];a[i]:=t;
if (count mod 5=0) then writeln;
end; exit; end;
for i:=j to n do begin
t:=a[j];a[j]:=a[i];a[i]:=t;由OIFans.cn收集
③ ;
t:=a[j]; ④ ;
end end; begin
writeln('Entry n,k (k<=n):'); read(n,k);
count:=0;
for i:=1 to n do a[i]:=i;
⑤ ;
end.
2．（TSP 问题的交叉算子）TSP 问题(Traveling Salesman Problem)描述如下：给定 n 个城 市，构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等），现要构造遍历所有城市的环 路，每个城市恰好经过一次，求使总代价达到最小的一条环路。
遗传算法是求解该问题的一个很有效的近似算法。在该算法中，一个个体为一条环路，其编码方法 之一是 1 到 n 这 n 个数字的一个排列，每个数字为一个城市的编号。例如当 n=5 时，“3 4 2 1 5” 表示该方案实施的路线为 3->4->2->1->5->3。遗传算法的核心是通过两个个体的交叉操作，产生两 个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：
(1)选定中间一段作为互换段，该段的起止下标为 t1，t2，随机生成 t1，t2 后，互换两段。
(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：
(2.1) 将两个互换段中，共同的数字标记为 0，表示已处理完。
(2.2) 将两个互换段中其余数字标记为 1，按顺序将互换段外重复的数字进行替换。 例如：n=12，两个个体分别是：
a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11
a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9
t1=5，t2=8。上述每一行中，两个星号间的部分为互换段。假定数组的下标从 1 开始，互换后有：
a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11
a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9
然后，将数字 6,7 对应的项标记为 0，星号内数字 2,9,10,11 对应的项标记为 1，并且按顺序对 应关系为:10<->2，11<->9。于是，将 a1[9]=10 替换为 a1[9]=2，将 a2[2]=2 替换为 a2[2]=10， 类似再做第 2 组替换。这样处理后，就得到了两个新个体：
a1: 1 3 5 4 6 7 10 11 2 12 8 9
a2: 3 10 1 12 2 6 7 9 8 5 4 11
（3）输出两个新个体的编码。 程序：
program ex502;
type arr1=array[1..20] of integer;
var a1,a2,kz1,kz2:arr1; n,k,t1,t2:integer;
function rand1(k:integer):integer;
var t:integer;
begin t:=0;
while (t<2) or(t>k) do t:=random(k+1)-2; rand1:=t;
end;
procere read1(var a:arr1;m:integer);
{读入数组元素 a[1]至 a[m]，a[0]=0，略。}
procere wrt1(var a:arr1;m:integer);
{输出数组元素 a[1]至 a[m]，略。}
procere cross(var a1,a2:arr1;t1, t2,n:integer);由OIFans.cn收集
var i,j,t,kj:integer; begin
for i:=t1 to t2 do begin
t:=a1[i]; ① ;
end;
for i:=1 to n do
if (i<t1)or(i>t2) then begin
kz1[i]:=-1;kz2[i]:=-1;
end else
begin ② ; end;
for i:=t1 to t2 do for j:=t1 to t2 do
if(a1[i]=a2[j]) then
begin ③ ; break; end;
for i:=t1 to t2 do if(kz1[i]=1) then begin
for j:=t1 to t2 do if(kz2[j]=1) then
begin kj:=j; break; end;
for j:=1 to n do if ④ then
begin a1[j]:=a2[kj];break; end;
for j:=1 to n do if ⑤ then
begin a2[j]:=a1[i]; break; end;
kz1[i]:=0;kz2[kj]:=0;
end; end; begin
writeln('input (n>5):');
readln(n);
writeln('input array 1:'); read1(a1,n);
writeln('input array 2:'); read1(a2,n);
t1:=rand1(n-1);
repeat
t2:=rand1(n-1); until(t1<>t2); if(t1>t2) then
begin k:=t1; t1:=t2; t2:=k; end;
⑥ ;
wrt1(a1,n); wrt1(a2,n);
end.
2005：
1．木材加工
题目描述:
木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有
剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务
是计算能够得到的小段木头的最大长度。
木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度
也是正整数。
输入:
第一行是两个正整数N和K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N是原木的数目，
K是需要得到的小段的数目。
接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。
输出:
输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。
输入样例:
3 7
232
124
456
输出样例:
114
程序：
var
n, k : integer;
len : array [1..10000] of integer;
i, left, right, mid : integer;
function isok(t : integer) : boolean;
var
num, i : integer;
begin
num := 0;
for i := 1 to n do begin
if num >= k then break;
num := ① ;
end;
if ② then isok := true
else isok := false;
end;
begin
readln(n, k);
right := 0;
for i := 1 to n do begin
readln(len[i]);
if right < len[i] then right := len[i];
end;
inc(right);
③ ;
while ④ < right do begin
mid := (left + right) div 2;
if ⑤ then right := mid
else left := mid;
end;
writeln(left);
end.
2．N叉树
题目描述:
我们都了解二叉树的先根遍历，中根遍历和后根遍历。当知道先根遍历的结果和中根遍
历结果的时候，我们可以唯一的确定二叉树；同样的，如果知道了后根遍历的结果和中根遍
历结果，二叉树也是唯一确定的。但是如果只知道先根遍历和后根遍历的结果，二叉树就不
是唯一的了。但是我们可以计算满足条件的不同二叉树一共有多少个。这不是一个很困难的
问题，稍微复杂一点，我们把这个问题推广到N叉树。
我们用小写英文字母来表示N 叉树的结点，不同的结点用不同的字母表示。比如，对
于4叉树，如果先根遍历的结果是abdefgc，后根遍历的结果是defgbca，那么我们可以
得到6个不同的4叉树（如下图）。
输入:
输入数据包括3行。
第一行是一个正整数N(2 ≤ N ≤ 20)，表示我们要考虑N叉树。
第二行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。
输出:
输出不同的N叉树的数目。题目中给的数据保证得到的结果小于2
31
。
输入样例:
4
abdefgc
defgbca
输出样例:
6
程序：
var
str1, str2 : string;
N, len : integer;
com : array[0..100, 0..100] of longint;
function getcom(x, y : integer) : longint;
begin
if (y = 0) or (x = y) then ①
else if com[x][y] <> 0 then getcom := com[x][y]
else begin
com[x][y] := getcom(x - 1, y)+ ② ;
getcom := com[x][y];
end;
end;
function count(a, b, c : integer) : longint;
var
sum : longint;
k, s, t, p : integer;
begin
sum := 1; k := 0; s := a + 1; t := c;
if a = b then count := 1
else begin
while s <= b do begin
p := t;
while str1[s] <> str2[t] do inc(t);
sum := sum * count(s, s + t - p, p);
s := ③ ;
④ ; inc(k);
end;
count := ⑤ * getcom(N, k);
end;
end;
begin
readln(N); readln(str1); readln(str2);
len := length(str1);
writeln(count( ⑥ ));
end.
2004：
1．Joseph
题目描述:
原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，m=5的时候，出列的顺序依次是5，4，6，2，3，1。
现在的问题是：假设有k个好人和k个坏人。好人的编号的1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人。
输入:
仅有的一个数字是k（0 < k <14）。
输出:
使得最先出列的k个人都是坏人的m的最小值。
输入样例:
4
输出样例:
30
程序：
program program1;
var
i, k, m, start: longint;
find: boolean;
function check(remain: integer): boolean;
var result: integer;
begin
result:=( ① ) mod remain;
if( ② )then begin
start := result; check := true;
end
else check := false;
end;
begin
find := false;
read(k);
m := k;
while ( ③ ) do begin
find := true; start := 0;
for i := 0 to k-1 do
if( not check( ④ )) then begin
find := false; break;
end;
inc(m);
end;
writeln( ⑤ );
end.
2．逻辑游戏
题目描述:
一个同学给了我一个逻辑游戏。他给了我图1，在这个图上，每一段边界都已经进行了编号。我的任务是在图中画一条连续的曲线，使得这条曲线穿过每一个边界一次且仅穿过一次，而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。
对于图1，我的同学告诉我画出这样的一条曲线（图2）是不可能的，但是对于有的图形（比如图3），画出这样一条曲线是可行的。对于给定的一个图，我想知道是否可以画出满足要求的曲线。
图1 图2
图3 图4
输入:
输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间（包括0和255）的整数。处于同一个区域的单元里的数相同，相邻区域的数不同（但是不相邻的区域里的数可能相同）。
输入的第一行是n（0<n<100）。以下的n行每行包括n个整数，分别给出对应的单元里的整数（这n个整数之间用空格分开）。图4给出了输入样例对应的图形。
输出:
当可以画出满足题意的曲线的时候，输出“YES”；否则，输出“NO”。
输入样例:
3
1 1 2
1 2 2
1 1 2
输出样例:
YES
程序：
program program2;
const
d: array[0..7] of integer = (1, 0, -1, 0, 0, 1, ① );
var
orig, n, i, j, ns: integer;
a: array[0..101, 0..101] of integer;
bun: boolean;
procere plimba(x, y: integer);
var i, x1, y1: integer;
begin
a[x, y] := -a[x, y];
if (abs(a[x - 1, y]) <> orig) and (( ② <> a[x - 1, y])
or (abs(a[x, y - 1]) <> orig)) then inc(ns);
if (abs(a[x + 1, y]) <> orig) and ((a[x + 1, y - 1] <> a[x + 1,y])
or (abs(a[x, y - 1]) <> orig)) then inc(ns);
if (abs(a[x, y - 1]) <> orig) and (( ③ <> a[x, y - 1])
or (abs(a[x - 1, y]) <> orig)) then inc(ns);
if (abs(a[x, y + 1]) <> orig) and ((a[x - 1, y + 1] <> a[x,y + 1])
or (abs(a[x - 1, y]) <> orig)) then inc(ns);
for i := 0 to 3 do begin
x1 := x + d[2 * i];y1:=y+ ④ ;
if (x1 >= 1) and (x1 <= n) and (y1 >= 1) and (y1 <= n) and
( ⑤ ) then plimba(x1, y1);
end;
end;
begin
bun := true;
read(n);
for i := 0 to n+1 do
for j := 0 to n+1 do a[i, j] := 0;
a[0, 0] := -1; a[n + 1, 0] := -1;
a[0, n + 1] := -1; a[n + 1, n + 1] := -1;
for i := 1 to n do
for j := 1 to n do read(a[i, j]);
for i := 1 to n do
for j := 1 to n do
if a[i, j] > -1 then begin
ns := 0; ⑥ ;
plimba(i, j);
if ns mod 2 = 1 then bun := false;
end;
if bun then writeln('YES');
if not bun then writeln('NO');
end.
2003：
1. 翻硬币
题目描述：
一摞硬币共有m枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的2枚硬币，将他们一起翻面后放回原处。在取3枚，取4枚……直至m枚。然后在从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中每一枚又是正面朝上为止。例如，m为1时，翻两次即可。
输 入：仅有的一个数字是这摞硬币的枚数m ，0< m <1000。
输 出：为了使这摞硬币中的每一枚都是朝正面朝上所必须翻的次数。
输入样例：30
输出样例：899
程 序：
program Program1;
var m:integer;
function solve(m: integer):integer;
var i,t,d: integer;
flag: Boolean;
begin
if (m = 1) then
solve := (1)
else begin
d := 2*m+1; t := 2; i := 1; flag := False;
repeat
if (t = 1) then
begin
solve := (2) ; flag := True;
end
else if ( (3) ) then
begin
solve := i*m-1; flag := True;
end
else
t := (4) ;
i:=i+1;
until flag;
end
end;
begin
read(m); if (( (5) ) and (m<1000)) then
writeln( (6) );
end.
2. OIM地形
题目描述：
二维离散世界有一种地形叫OIM(OI Mountain)。这种山的坡度只能上升('/')或下降('\'),而且两边的山脚都与地平线等高,山上所有地方都不低于地平线.例如：
/\ /\
/ \/\ 是一座OIM；而 / \ 不是。
\/
这个世界的地理学家们为了方便纪录，给OIM所有可能的形状用正整数编好号，而且每个正整数恰好对应一种山形。他们规定，若两座山的宽度不同，则较宽的编号较大；若宽度相同，则比较从左边开始第1个坡度不同的地方，坡度上升的编号较大。以下三座OIM的编号有小到大递增：
/\ /\ /\ /\
/ \/\ / \/\/\ / \/ \。显然/\的编号为1。但是地理学家在整理纪录是发觉，查找编号与山形的对应关系不是很方便。他们希望能快速地从编号得到山的形状。你自告奋勇答应他们写一个程序，输入编号，能马上输出山形。
输 入：一个编号（编号大小不超过600,000,000），
输 出：输入编号所对应的山形，1座山所占行数恰为它的高度，即山顶上不能有多余空行。
输入样例：15
输出样例： /\ /\
/ \/ \
程 序：
program Program2;
const
L:integer =19; SZ: integer =50;
UP: char = '/'; DN: char = '\';
Var
i,nth,x,y,h,e,f:integer;
m: array[0..1,0..38,0..19] of integer;
pic: array[0..49,0..49] of char;
procere init;
var k,s,a,b,c: integer;
begin
for a:=0 to 1 do
for b:=0 to 2*L do
for c:=0 to L do
m[a,b,c]:=0; m[0,0,0]:=1;
for k:=0 to 2*L-1 do
begin
for s:=1 to L do
begin
m[0,k+1,s] := m[0,k,s+1] + m[1,k,s+1];
m[1,k+1,s]:= (1) ;
end;
m[0,k+1,0] :=m[0,k,1]+m[1,k,1];
end;
end;
procere draw(k,s,nth:integer);
begin
if (k=0) then exit;
if ((nth-m[1,k,s])>=0) then
begin
nth:=nth-m[1,k,s];
if (y>h) then (2) ;
pic[y,x]:=UP; y:=y+1; x:=x+1; draw( (3) );
end
else begin
y:=y - 1; pic[y,x]:=DN; x:=x+1; draw(k-1,s-1,nth);
end;
end;
begin
init;
read(nth);
for e:=0 to SZ-1 do
for f:=0 to SZ-1 do
pic[e,f]:= ' ';
x:=0;
y:=0
h:=0;
i:=0;
while ((nth-m[0,2*i,0])>=0) do
begin
nth:= nth-m[0,2*i,0];
(4) ;
end;
draw( (5) );
for i:=h downto x-1 do
begin
for e:=0 to x-1 do
write(pic[i,e]);
writeln(' ');
end;
end.
2002：
1． 问题描述：工厂在每天的生产中，需要一定数量的零件，同时也可以知道每天生产一个零件的生产单价。在N天的生产中，当天生产的零件可以满足当天的需要，若当天用不完，可以放到下一天去使用，但要收取每个零件的保管费，不同的天收取的费用也不相同。
问题求解：求得一个N天的生产计划（即N天中每天应生产零件个数），使总的费用最少。
输入：N（天数 N<=29）
每天的需求量（N个整数）
每天生产零件的单价（N个整数）
每天保管零件的单价（N个整数）
输出：每天的生产零件个数（N个整数）
例如：当N=3时，其需要量与费用如下：
第一天 第二天 第三天
需 要 量 25 15 30
生产单价 20 30 32
保管单价 5 10 0
生产计划的安排可以有许多方案，如下面的三种：
第一天 第二天 第三天 总的费用
25 15 30 25*20+15*30+30*32=1910
40 0 30 40*20+15*5+30*32=1835
70 0 0 70*20+45*5+30*10=1925
程序说明：
b[n]：存放每天的需求量
c[n]：每天生产零件的单价
d[n]：每天保管零件的单价
e[n]：生产计划
程序：
program exp5;
var
i,j,n,yu,j0,j1,s : integer ;
b,c,d,e : array[0..30] of integer ;
begin
readln(n);
for i:=1 to n do readln(b[i],c[i],d[i]);
for i:=1 to n do e[i]:=0;
①__________:=10000; c[n+2]=0; b[n+1]:=0 j0:=1;
while (j0<=n) do
begin
yu:=c[j0]; j1:=j0; s:=b[j0];
while ②__________ do
begin
③__________ j1:=j1+1; s:=s+b[j1];
end;
④__________ j0:=j1+1;
end;
for i:=1 to n do ⑤__________
readln;
end.
二．问题描述：有n种基本物质（n≤10），分别记为P1，P2，……，Pn，用n种基本物质构造物质，这些物品使用在k个不同地区（k≤20），每个地区对物品提出自己的要求，这些要求用一个n位的数表示：a1a2……a n，其中：
ai = 1表示所需物质中必须有第i种基本物质
= -1表示所需物质中必须不能有第i种基本物质
= 0无所谓
问题求解：当k个不同要求给出之后，给出一种方案，指出哪些物质被使用，哪些物质不被使用。
程序说明：数组 b[1],b[2]……b[n] 表示某种物质
a[1..k,1..n] 记录k个地区对物品的要求，其中：
a[i,j]=1 表示第i个地区对第j种物品是需要的
a[i,j]=0 表示第i个地区对第j种物品是无所谓的
a[i,j]= -1 表示第i个地区对第j种物品是不需要的
程序：
program gxp2;
var
i,j,k,n : integer ;
p : boolean ;
b : array[0..20] of 0..1 ;
a : array[1..20,1..10] of integer ;
begin
readln(n,k);
for i:=1 to k do
begin
for j:=1 to n do read(a[i,j]);
readln;
end;
for i:=0 to n do b[i]:=0;
p:=true;
while ①__________ do
begin
j:=n;
while b[j]=1 do j:=j-1;
②__________
for i:=j+1 to n do b[i]:=0;
③__________
for i:=1 to k do
for j:=1 to n do
if (a[i,j]=1) and (b[j]=0) or ④__________
then p:=true;
end;
if ⑤__________
then writeln(‘找不到！’)
else for i:=1 to n do
if (b[i]=1) then writeln(‘物质’,i,’需要’)
else writeln(‘物质’,i,’不需要’);
end.
2001：
1.存储空间的回收算法。设在内存中已经存放了若干个作业A，B，C，D。其余的空间为可用的(如图一中(a))。
此时，可用空间可用一个二维数组dk[1..100，1..2 ]表示，(如下表一中(a))，其中：dk[i，1]对应第i个可用空间首址，dk[i，2]对应第i个可用空间长度如上图中，dk：
100 50
300 100
50 100
0 0
100 50
300 100
500 100
10000 0
表一(a) 表一(b)
现某个作业释放一个区域，其首址为d，长度为L，此时将释放区域加入到可用空间表中。要求在加入时，若可用空间相邻时，则必须进行合并。因此出现下面的4种情况(如上图一(b)所示)。
(1)下靠，即回收区域和下面可用空间相邻，例如，d=80，L=20，此时成为表二中的(a)。
(2)上靠，例如，d=600，L=50，此时表成为表二中的(b)。
(3)上、下靠，例如，d=150，L=150，此时表成为表二中的(c)。
(4)上、下不靠，例如，d=430，L=20，此时表成为表二中的(d)。
80 70
300 100
50 100
100 50
300 100
500 150
100
300
500
100
100 50
300 100
430 20
500 100
表二(a)(下靠) 表二(b)(上靠) 表二(c)(上，下靠) 表二(d)(上，下不靠)
程序说明：对数组dk预置2个标志，即头和尾标志，成为表二中(b)，这样可使算法简单，sp为dk表末地址。
程序清单：
PROGRAM GAO7_5；
VAR I，J，SP，D，L：INTEGER；
DK ：ARRAY[0..100，1..2]OF INTEGER；
BEGIN
READLN(SP)；
FOR I:=1 TO SP DO
READLN(DK[I，1]，DK[I，2])；
DK[0，1]:=0；DK[0，2]:=0； ① ；
DK[SP，1]:=10000；DK[SP，2]:=0；READLN(D，L)；I:=1；
WHILE DK[I，1]<D DO I:=I+1； ② ；
IF(DK[I，1]+DK[I，2]=D)THEN
IF(D+L=DK[I+1，1])THEN
BEGIN
DK[I，2]:= ③ ；
FOR J:=I+1 TO SP-1 DO
DK[J]:=DK[J+1]；
SP：=SP-1；
END
ELSE DK[I，2]:=DK[I，2]+L
ELSE IF(D+L=DK[I+1，1])THEN
BEGIN
DK[I+1，1]::= ④ ；DK[I+1，2]:=DK[I+1，2]+L
END
ELSE BEGIN
FOR J:=SP DOWNTO I+1 DO DK[J+1]:=DK[J]；
⑤ :=D； DK[I+1，2]:=L；SP:=SP+1；
END；
FOR I:=1 TO SP-1 DO WRITELN(DK[I，1]:4，DK[I，2]:4)；READLN；
END.
2.求关键路径
设有一个工程网络如下图表示(无环路的有向图)：
其中，顶点表示活动，①表示工程开始，⑤表示工程结束(可变，用N表示)，边上的数字表示活动延续的时间。
如上图中，活动①开始5天后活动②才能开始工作，而活动③则要等①、②完成之后才能开始，即最早也要7天后才能工作。
在工程网络中，延续时间最长的路径称为关键路径。上图中的关键路径为：①—②—③—④—⑤共18天完成。
关键路径的算法如下：
1.数据结构：
R[1..N，1..N]OF INTEGER； 表示活动的延续时间，若无连线，则用-1表示；
EET[1..N] 表示活动最早可以开始的时间
ET[1..N] 表示活动最迟应该开始的时间
关键路径通过点J，具有如下的性质：EET[J]=ET[J]
2.约定：
结点的排列已经过拓扑排序，即序号前面的结点会影响序号后面结点的活
④ 如何计算关键路径
并行的活动：最早结束时间大者，在关键路径。以网上一图举例。
A-->B/C并列，其中C活动最早结束时间（EalyFinish）为第13天，大于7，所以C在关键路径上。
A-->C-->D/E,23>18,同上
A-->C-->D-->G,同上
A-->C-->D-->G-->H，同上
⑤ 求关键路径的程序（最好是C#的，其他的也可以）
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
namespaceToppath
{
classProgram
{
staticvoidMain(string[]args)
{
node<char>[]Mynode={newnode<char>('A'),newnode<char>('B'),newnode<char>('C'),
newnode<char>('D'),newnode<char>('E'),newnode<char>('F'),
newnode<char>('G'),newnode<char>('H'),newnode<char>('I'),
newnode<char>('J')};
GraphAdjlist<char>xiong=newGraphAdjlist<char>(Mynode);
xiong.SetEdge(Mynode[0],Mynode[1],3);
xiong.SetEdge(Mynode[0],Mynode[2],4);
xiong.SetEdge(Mynode[1],Mynode[3],5);
xiong.SetEdge(Mynode[1],Mynode[4],6);
xiong.SetEdge(Mynode[2],Mynode[3],8);
xiong.SetEdge(Mynode[2],Mynode[5],7);
xiong.SetEdge(Mynode[3],Mynode[4],3);
xiong.SetEdge(Mynode[4],Mynode[7],4);
xiong.SetEdge(Mynode[4],Mynode[6],9);
xiong.SetEdge(Mynode[5],Mynode[7],6);
xiong.SetEdge(Mynode[7],Mynode[8],5);
xiong.SetEdge(Mynode[6],Mynode[9],2);
xiong.SetEdge(Mynode[8],Mynode[9],3);
xiong.toppath();
Console.ReadKey();
}
}
classnode<T>
{
publicTData
{get;set;}
publicnode(Ttemp)
{
Data=temp;
}
}
classvextable<T>
{
publicnode<T>Vex
{get;set;}
publicadjlistnode<T>First
{get;set;}
publicintIn
{get;set;}
publicvextable()
{
Vex=null;
First=null;
}
publicvextable(node<T>p)
{
Vex=p;
First=null;
In=0;
}
}
classadjlistnode<T>
{
publicintIndex
{get;set;}
publicadjlistnode<T>next
{get;set;}
publicintWeight
{get;set;}
publicadjlistnode(intindex)
{
Index=index;
next=null;
Weight=0;
}
publicadjlistnode()
{
Index=-1;
next=null;
Weight=0;
}
}
classGraphAdjlist<T>
{
publicvextable<T>[]vext
{get;set;}
publicint[]Visited
{get;set;}
publicvextable<T>this[intindex]
{
get{returnvext[index];}
set{vext[index]=value;}
}
publicGraphAdjlist(node<T>[]mynode)
{
vext=newvextable<T>[mynode.Length];
Visited=newint[mynode.Length];
for(inti=0;i<mynode.Length;i++)
{
vext[i]=newvextable<T>(mynode[i]);
}
}
publicintIndexofvertex(node<T>x)
{
for(inti=0;i<vext.Length;i++)
{
if(vext[i].Vex.Equals(x))
returni;
}
Console.WriteLine("nothisnode");
return-1;
}
publicvoidSetEdge(node<T>v1,node<T>v2,intv)//这个Top排序要使用的是一个有向邻接表才对
{
intiv1=Indexofvertex(v1);
intiv2=Indexofvertex(v2);
adjlistnode<T>p1=newadjlistnode<T>(iv1);
adjlistnode<T>p2=newadjlistnode<T>(iv2);
//在v1处添加v2;
p2.next=vext[iv1].First;
vext[iv1].First=p2;
p2.Weight=v;
vext[iv2].In++;//添加入度
}
publicvoidtoppath()
{
Stack<int>temp=newStack<int>();//用什么都行，但必须保持一致用于存放拓扑坐标
Stack<int>toparray=newStack<int>();//用stack最好，因为正向过去算etv，反向回来算ltv，先入后出最好
Stack<int>path=newStack<int>();//再反一次，存的就是正常的拓扑图，从头开始那种
intp=-1;intm=-1;
adjlistnode<T>q=newadjlistnode<T>();
int[]etv=newint[vext.Length];//最早点
int[]ltv=newint[vext.Length];//最晚点
intete=-1;//最早边，是判断变量不是数组用来找边的
intlte=-1;//最晚边
intk=0;
for(inti=0;i<vext.Length;i++)
{
if(vext[i].In==0)
{
temp.Push(i);//压入序号
}
}
while(toparray.Count!=vext.Length)
{
p=temp.Pop();
toparray.Push(p);
q=vext[p].First;
while(q!=null)
{
vext[q.Index].In--;//下标就用最原始的值，顺序用栈保存好就行
if(vext[q.Index].In==0)
{
temp.Push(q.Index);
}
if(etv[p]+q.Weight>etv[q.Index])//正向过去算etv,etv均初始化为0
{
etv[q.Index]=etv[p]+q.Weight;
}
q=q.next;
}
}//栈就是用来压和弹的，如果想取完还有，那就在找个栈，边取边存，不是给你拿来遍历用的
for(inti=0;i<vext.Length;i++)//找到etv的最大值拿来赋值给ltv因为这是反向回去，最大值是终点值
{
if(etv[i]>m)
{
m=etv[i];
}
}
while(toparray.Count!=0)
{
k=toparray.Pop();//由于是栈所以弹出的肯定是终点
path.Push(k);//再保存一次
q=vext[k].First;
ltv[k]=m;//将所有最晚顶点置成最大值
while(q!=null)
{
if((ltv[q.Index]-q.Weight)<ltv[k])//算ltv其实是min
{
ltv[k]=ltv[q.Index]-q.Weight;
}
q=q.next;
}
}
while(path.Count!=0)//这边我感觉还是按拓扑顺序得好，因为这样可以有序的排列顶点，不按也成反正是找边，边构成路
{
inti=path.Pop();
q=vext[i].First;
while(q!=null)
{
ete=etv[i];//边上的值，其实看etv和etl就能看到，只不过用这种方式更加形象的定位到边，并且给出权值
lte=ltv[q.Index]-q.Weight;
if(ete==lte)
{
Console.WriteLine(vext[i].Vex.Data+""+vext[q.Index].Vex.Data+""+q.Weight);
}
q=q.next;
}
}
Console.ReadKey();
}
}
}
朋友看得懂不，不懂可以加我QQ：1036433209,也许你已成为大神，就当一起学习吧
⑥ 求如下有向图的关键路径以及任意两点之间的最短距离
用CPM算法求有向图的关键路径和用Dijkstra算法求有向图的最短路径的C语言程序如下
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
#define INF 32767 // 此处修改最大值
#define nLENGTH(a) (sizeof(a)/sizeof(a[0]))
#define eLENGTH(a) (sizeof(a)/sizeof(char))/(sizeof(a[0])/sizeof(char))
typedef struct _graph{
char vexs[MAX]; // 顶点集合
int vexnum; // 顶点数
int edgnum; // 边数
int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;
// 边的结构体
typedef struct _EdgeData{
char start; // 边的起点
char end; // 边的终点
int weight; // 边的权重
}EData;
//指向节点的位置
int point_node(PGraph g,char c){
for(int i=0;i<g->vexnum;i++){
if(g->vexs[i]==c){
return i;
}
}
return -1;
}
PGraph create_graph(int b[][3],char a[],int n,int e){
char c1,c2; //边的2个顶点
PGraph g; //矩阵
g=(PGraph)malloc(sizeof(Graph));
//memset()第一个参数 是地址，第二个参数是开辟空间的初始值，第三个参数是开辟空间的大小
memset(g, 0, sizeof(Graph));
printf("顶点个数: ");//顶点数
g->vexnum=n;
printf("%d ",g->vexnum);
printf("边个数: ");//边数
g->edgnum=e;
printf("%d ",g->edgnum);
//初始化顶点
for(int j=0;j<g->vexnum;j++){
g->vexs[j]=a[j];
}
for(int i=0;i<g->edgnum;i++){
int p1,p2;
c1=char(b[i][0]);
c2=char(b[i][1]);
p1=point_node(g, c1);
p2=point_node(g, c2);
if (p1==-1 || p2==-1){
printf("input error: invalid edge! ");
free(g);
continue;
}
g->matrix[p1][p2]=b[i][2];
}
for(int i=0;i<g->vexnum;i++){
for(int j=0;j<g->vexnum;j++){
if(g->matrix[i][j]==0)
g->matrix[i][j]=INF;
}
}
return g;
}
//关键路径的最短时间
//关键路径法（Critical Path Method，CPM）
void CPM_road(PGraph g){
int i,j;
int a[MAX]={0},b[MAX]={-10};
int max=0;//最长路径
for( i=0;i<g->vexnum;i++){//列数遍历
for( j=0;j<g->vexnum;j++){//行数遍历
//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，
//加上g->matrix[j][i]的路径就是当前a[i]的路径
if(g->matrix[j][i]!=INF && g->matrix[j][i]+a[j]>max){
max=g->matrix[j][i]+a[j];
a[i]=max;
}
}
max=0;
}
//显示最长路径
printf("第一个顶点到每一个顶点的最长路径:");
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("V%d ",i+1);
}
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("%d ",a[i]);
}
printf(" ");
printf("最后一个顶点到每个顶点的最长路径:");
for( i=g->vexnum-1;i>=0;i--){ //列数遍历
for( j=g->vexnum-1;j>=0;j--){ //行数遍历
//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，
//加上g->matrix[j][i]的路径就是当前a[i]的路径
if(g->matrix[i][j]!=INF && g->matrix[i][j]+b[j]>max){
max=g->matrix[i][j]+b[j];
b[i]=max;
}
}
max=0;
}
//显示最长路径
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("V%d ",i+1);
}
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("%d ",b[i]);
}
printf(" ");
printf("关键路径: ");
for(i=0;i<g->vexnum;i++){
if(a[i]==a[g->vexnum-1]-b[i]){
printf("V%c ",g->vexs[i]);
}
}
printf(" ");
}
void print_shortest_path(PGraph g,int* distance,int* path,int* used,int start,int end){
// 输出最短距离并打印最短路径
int i = 0, pre, inverse_path[g->vexnum];
char s1[3],s2[3];
sprintf(s1, "V%d", (start+1));
sprintf(s2, "V%d", (end+1));
printf("从%s顶点到%s顶点的最短距离: %d ", s1, s2, distance[end]);
inverse_path[i] = end;
pre = path[end];
if(pre == -1){
printf("没有通路! ");
}else{
while(pre != start){
inverse_path[++i] = pre;
pre = path[pre];
}
inverse_path[++i] = start;
printf("从%s顶点到%s顶点的最短路径: ", s1, s2);
for(; i > 0; i--){
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s -> ", s1);
}
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s ", s1);
}
return;
}
void shortest_path(PGraph g,int start, int end){ // 基于Dijkstra算法的最短路径函数
int distance[g->vexnum]; // 用于存放起始点到其余各点的最短距离
int path[g->vexnum]; // 用于存放起始点到其余各点最短路径的前一个顶点
int used[g->vexnum] = { 0 }; // 用于标记该顶点是否已经找到最短路径
int i, j, min_node, min_dis, pass_flag = 0;
for(i = 0; i < g->vexnum; i++){
distance[i] = g->matrix[start][i]; // 初始化距离数组
if(g->matrix[start][i] < INF){
path[i] = start; // 初始化路径数组
}else{
path[i] = -1;
}
}
used[start] = 1;
path[start] = start;
for(i = 0; i < g->vexnum; i++){
min_dis = INF;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0 && distance[j] < min_dis){
min_node = j;
min_dis = distance[j];
pass_flag++; // 标记是否存在通路
}
}
if(pass_flag != 0){
used[min_node] = 1;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0){
if(g->matrix[min_node][j] < INF && distance[min_node] + g->matrix[min_node][j] < distance[j]){
distance[j] = distance[min_node] + g->matrix[min_node][j];
path[j] = min_node;
}
}
}
}
}
print_shortest_path(g,distance, path, used, start, end);
return;
}
int main(){
int i,j;
PGraph gp;
char a[]={'1', '2', '3', '4', '5', '6', '7'};
int b[][3]={{'1', '2',3},
{'1', '3',2},
{'1', '4',6},
{'2', '4',2},
{'2', '5',4},
{'3', '4',1},
{'3', '6',3},
{'4', '5',1},
{'5', '7',3},
{'6', '7',4}};
int n=nLENGTH(a);
int e=eLENGTH(b);
gp=create_graph(b,a,n,e);
//打印邻接矩阵
printf("邻接矩阵: ");
for (i = 0; i < gp->vexnum; i++){
for (j = 0; j < gp->vexnum; j++)
printf("%d ", gp->matrix[j][i]);
printf(" ");
}
CPM_road(gp);
printf(" ");
for(i=0;i<gp->vexnum;i++){
for(j=0;j<gp->vexnum;j++){
if(i!=j)
shortest_path(gp,i, j);
}
}
return 0;
}
运行结果