第5章贪心算法
在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心算法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所做的选择可以依赖于以往所做过的选择，但既不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。
当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是在当前状态下具有某种意义的最好选择，即贪心选择，并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解，而且所给出的算法一般比动态规划算法更加简单、直观和高效。





5．1活动安排问题
活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
设有n个活动的集合E＝{1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si＜fi。如果选择了活动i，则它在半开时间区间［si，fi)内占用资源。若区间［si，fi)与区间［sj，fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
为了编程方便，我们把活动的起始时间和结束时间定义为结构体： 

struct action{

int s;					　　//起始时间

int f;					　　//结束时间

int index;				　　//活动的编号

};

活动的集合E记为数组： 

action a［1000］;

然后按活动的结束时间升序排序： a［1］．f≤a［2］．f≤…≤a［n］．f。排序比较因子： 

bool cmp(const action &a, const action &b)

{

if (a.f<=b.f) return true;

return false;

}

使用标准模板库函数排序(下标0未用)： 

sort(a+1, a+n+1, cmp);

计算活动安排问题的贪心算法，如算法5．1所示。
算法5．1计算活动安排问题的贪心算法。

//形参数组b用来记录被选中的活动

void GreedySelector(int n, action a［］, bool b［］)

{

b［1］ = true;				　　//第1个活动是必选的

//记录最近一次加入集合b中的活动

int preEnd = 1;

for(int i=2; i<=n; i++)

if (a［i］.s>=a［preEnd］.f)

{

b［i］ = true;

preEnd = i; 

}

} 

算法实现源代码： actionArrangement．cpp。
活动i在集合b中，当且仅当b［i］的值为true。变量preEnd用来记录最近一次加入集合b中的活动。算法greedySelector首先选择活动1，并将preEnd初始化为1，然后依次检查活动i是否与当前已经选择的所有活动相容。若相容则将活动i加入已选择活动的集合b中，否则放弃，继续检查下一活动与集合b中活动的相容性。
例如有11个活动，其开始时间和结束时间如表51所示，并按结束时间升序排列。


表51样例数据(11个活动)


i
1
2
3
4
5
6
7
8
9
10
11
a［i］．s
1
3
0
5
3
5
6
8
8
2
12
a［i］．f
4
5
6
7
8
9
10
11
12
13
14
b
1
0
0
1
0
0
0
1
0
0
1

由于输入的活动按完成时间升序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合b中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。该算法的贪心选择意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
算法5．1的计算过程，如图51所示。


图51活动安排问题的几何意义


根据数组b的值，就可以输出选中的活动编号： 

for(int i=1; i<=n;i++)

if(b［i］) printf("%d ",a［i］.index);

printf("＼n");

当输入的活动已按结束时间升序排列，算法只需O(n)的时间来安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按升序排列，可用O(nlog2n)时间重排。
贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得整体最优解，即它最终所确定的相容活动集合b的规模最大。这个结论可以用数学归纳法证明，请参考文献［3］。





5．2贪心算法的理论基础
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪心选择。即希望通过问题的局部最优解来求出整个问题的最优解。这种算法是一种很简洁的方法，对许多问题它能产生整体最优解，但不能保证总是有效，因为它不是对所有问题都能得到整体最优解，只能说其解必然是最优解的很好近似值。
利用贪心算法解题，需要解决两个问题： 
(1) 该题是否适合用贪心算法求解； 
(2) 如何选择贪心标准，以得到问题的最优/较优解。
5．2．1贪心选择性质
贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
(1) 在动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题后才能做出选择。
(2) 在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。然后再解出这个选择后产生的相应的子问题。贪心算法所做的贪心选择可以依赖于以往所做的选择，但不依赖于将来所做的选择，也不依赖于子问题的解。
正是由于这种差别，动态规划算法通常以自底向上的方式解各个子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。
5．2．2最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心算法在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划算法则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退； 动态规划算法则会根据以前的选择结果对当前进行选择，有回退功能。动态规划算法主要运用于二维或三维问题，而贪心算法一般是一维问题。
5．2．3贪心算法的求解过程
使用贪心算法求解问题应该考虑如下几个方面： 
(1) 候选集合A： 为了构造问题的解决方案，有一个候选集合A作为问题的可能解，即问题的最终解均取自于候选集合A。
(2) 解集合S： 随着贪心选择的进行，解集合S不断扩展，直到构成满足问题的完整解。
(3) 解决函数solution： 检查解集合S是否构成问题的完整解。
(4) 选择函数select： 即贪心策略，这是贪心算法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。
(5) 可行函数feasible： 检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。
贪心算法的一般流程，如算法5．2所示。
算法5．2贪心算法的一般流程。

//A是问题的输入集合即候选集合

Greedy(A)

{

S={ };						　　//初始解集合为空集

while (not solution(S))	　　//集合S没有构成问题的一个解

{

x = select(A);		　　//在候选集合A中做贪心选择

if feasible(S, x)		　　//判断集合S中加入x后的解是否可行

S = S+{x};

A = A-{x};

}

return S;

｝






5．3背包问题
给定一个载重量为M的背包，考虑n个物品，其中第i个物品的质量为wi，价值为vi(1≤i≤n)，要求把物品装满背包，且使背包内的物品价值最大。有两类背包问题(根据物品是否可以分割)，如果物品不可以分割，称为01背包问题(见4．5节)； 如果物品可以分割，则称为背包问题，就是本节讨论的内容。
假设xi是物品i装入背包的部分(0≤xi≤1)，当xi＝0时表示物品i没有被装入背包； 当xi＝1时表示物品i被全部装入背包。根据问题的要求，该问题可形式化描述为： 

max∑ni=1pixi，s．t． ∑ni=1wixi=M

其中，0≤xi≤1。
假设背包的容量是50，有3个物品，如表52所示。


表52背包问题的3个物品


n
1
2
3
质量
10
20
30
价值
60
100
120
性价比
6
5
4

有3种方法来选取物品： 
(1) 当作01背包问题，采用动态规划算法，如图52(b)所示，获得最优值220； 
(2) 当作01背包问题，采用贪心算法，按性价比从高到低的顺序选取物品，获得最优值160，如图52(c)所示。由于物品不可分割，剩下的空间20，没有相应的物品可以装入而白白浪费。


图52背包问题与01背包问题的比较


(3) 当作背包问题，采用贪心算法，按性价比从高到低的顺序选取物品，获得最优值240，如图52(d)所示。由于物品可以分割，剩下的空间20，装入物品3的一部分，而获得了更好的性能。
从上面的分析可知，贪心算法对01背包问题不能得到最优解。当物品按性价比递减排序后，应用贪心算法可以得到最优解。该结论的证明，可以阅读参考文献［9］。
为了方便计算，建立如下的数据结构，表示物品的参数： 

struct bag{

int w;					　　//物品的质量

int v;					　　//物品的价值

double c;				　　//性价比

}a［1001］;					　　//存放物品的数组

排序因子(按性价比降序)： 

bool cmp(bag a,bag b){

if(a.c >b.c) return true;

return false;

}

使用标准模板库函数排序(最好使用stable_sort()函数，在性价比相同时保持输入的顺序)： 

sort(a, a+n, cmp);

按性价比排序后，背包问题的贪心算法如算法5．3所示。
算法5．3计算背包问题的贪心算法。

//形参n是物品的数量，c是背包的容量M，数组a是按物品的性价比降序排序

double knapsack(int n, bag a［］, double c)

{

double cleft = c;			　　//背包的剩余容量

int i = 0;

double b = 0;				　　//获得的价值

//当背包还能完全装入物品i

while(i<n && a［i］.w<cleft)

{

cleft -= a［i］.w;

b += a［i］.v; 

i++;

}

//装满背包的剩余空间

if (i<n) b += 1.0*a［i］.v*cleft/a［i］.w;

return b;

}

算法实现源代码： Knapsack．cpp。
如果要获得解向量X={x1，x2，…，xn}，则需要在数据结构中加入物品编号： 

struct bag{

int w;

int v;

double x;				　　//装入背包的量，0≤x≤1

int index;				　　//物品编号

double c;

}a［1001］;

获得解向量时，背包问题的贪心算法如算法5．4所示。
算法5．4计算背包问题的贪心算法，同时得到解向量。

double knapsack(int n, bag a［］, double c)

{

double cleft = c;

int i = 0;

double b = 0;

while(i<n && a［i］.w<=cleft)

{ 

cleft -= a［i］.w; 

b += a［i］.v;

//物品原先的序号是a［i］.index，全部装入背包

a［a［i］.index］.x = 1.0;

i++;

}

if (i<n) 

{

a［a［i］.index］.x = 1.0*cleft/a［i］.w;

b += a［a［i］.index］.x*a［i］.v;

}

return b;

}

算法实现源代码： Knapsackbest．cpp。





5．4最优装载问题
有一批集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
该问题的形式化描述为： 

max∑ni=1xi，s．t． ∑ni=1wixi≤c


其中xi∈{0，1}，1≤i≤n。
输入
本题有多组数据。
对于每组数据，第1行有两个数据： 第1个数据是轮船的载重量c(在整数范围内)，第2个数据是集装箱的数量n(1≤n≤100)。第2行有n个整数w1，w2，…，wn，整数之间用一个空格分开，这n个整数依次表示这n个集装箱的重量(1≤wi≤100，i＝1，2，…，n)。
输出
对每组数据，输出轮船在装载体积不受限制的情况下，最多能装载的集装箱数以及集装箱的编号。如果一个集装箱也装不进，就输出“No answer!”。
输入样例

50 3

40 10 40

37 5

10 30 24 35 40

25 3

30 40 50

输出样例

2

1 2

2

1 3

No answer!

【算法分析】
最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可以得到装载问题的最优解。表示集装箱的数据结构如下： 

struct load {

int index;				　　//集装箱编号

int w;					　　//集装箱质量

}box［1001］;

排序因子(按集装箱的质量升序)： 

bool cmp(load a, load b) {

if (a.w<b.w) return true;

else return false;

}

使用标准模板库函数排序(box［0］未使用)： 

stable_sort(box, box+n+1, cmp);

这是稳定排序函数，当重量相同时，保持输入数据原来的顺序。
最优装载问题的贪心算法如算法5．5所示。
算法5．5最优装载问题的贪心算法。

//输入数据和数组初始化

while (scanf("%d%d", &c, &n)!=EOF)

{

memset(box, 0, sizeof(box));

memset(x, 0, sizeof(x));

for (int i=1; i<=n; i++) 

{ 

scanf("%d", &box［i］.w);

box［i］.index = i;

}

//按集装箱的质量升序排序

stable_sort(box, box+n+1, cmp);

if (box［1］.w>c) {

printf("No answer!＼n");

continue;

}

//贪心算法的实现，质量最轻者先装载

int i;

for (i=1; i<=n && box［i］.w<=c; i++)

{

x［box［i］.index］ = 1;

c -= box［i］.w;

}

//输出装载的集装箱数量

printf("%d＼n",i-1);

//输出装载的集装箱编号

for (i=1; i<=n; i++)

if (x［i］) printf("%d ", i);

printf("＼n");

｝

算法实现源代码： Loading．cpp。





5．5单源最短路径
给定带权有向图G=(V，E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度，这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题(SingleSource Shortest Paths)。
如图53所示，就是要计算源点v1到其他各个顶点的最短距离，并输出相应的路径。


图53带权有向图G

输入
本题有多组数据。
第1行有两个数据n和m，其中n表示结点的个数，m表示路径的数目。
接下来有m行，每行都有3个数据s、t和edge，其中s表示路径的起点，t表示路径的终点，edge表示该路径的长度。
当n＝0，m＝0时，输入数据结束。
输出
源点(统一规定为顶点v1，虽然其他顶点也是可以的)到所有其他各顶点的最短路径长度。
接下来有n-1行，是从各个顶点(按升序)回到源点的路径。
输入样例

5 7

1 2 10

1 4 25

1 5 80

2 3 40

3 5 10

4 3 20

4 5 50

0 0

输出样例

10 45 25 55 

2<--1

3<--4<--1

4<--1

5<--3<--4<--1

【算法分析】
Dijkstra算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。初始时，S中仅含有源点。设u是G的某一个顶点，把从源点到u且中间只经过S中顶点的路径称为从源点到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从VS中取出具有最短特殊路径长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度。
Dijkstra算法的实现如算法5．6所示。
算法5．6计算单源最短路径问题的Dijkstra算法。

#define NUM 100

#define maxint 10000

//顶点个数n，源点v，有向图的邻接矩阵为c

//数组dist保存从源点v到每个顶点的最短特殊路径长度

//数组prev保存每个顶点在最短特殊路径上的前一个结点

void dijkstra(int n,int v,int dist［］,int prev［］,int c［］［NUM］)

{

int i,j;

bool s［NUM］;				　　//集合S

//初始化数组

for(i=1; i<=n; i++)

{

dist［i］ = c［v］［i］;

s［i］ = false;

if (dist［i］>maxint) prev［i］ = 0;

else prev［i］ = v;

}

//初始化源结点

dist［v］ = 0;

s［v］ = true;

for(i=1; i<n; i++)		　　//其余顶点

{

//在数组dist中寻找未处理结点的最小值

int tmp = maxint;

int u = v;

for(j=1; j<=n; j++)

if(!(s［j］) && (dist［j］<tmp))

{

u = j;

tmp = dist［j］;

}

s［u］ = 1;				　　//结点u加入S中

//利用结点u更新数组dist

for(j=1; j<=n; j++)

if(!(s［j］) && c［u］［j］<maxint)

{

//newdist为从源点到该点的最短特殊路径

int newdist = dist［u］+c［u］［j］;

if (newdist<dist［j］)

{

//修正最短距离

dist［j］ = newdist;

//记录j的前一个结点

prev［j］ = u;

}

}

}

}

算法实现源代码： ShortestPaths．cpp。
如图53所示的有向图G，邻接矩阵c的内容如表53所示。一对顶点(vi，vj)没有直接相连的边时，c［i］［j］=∞。数组dist［i］表示从源点到顶点vi的最短特殊路径长度。


表53有向图G的邻接矩阵


行/列
1
2
3
4
5
1
∞
10
∞
25
80
2
∞
∞
40
∞
∞
3
∞
∞
∞
∞
10
4
∞
∞
20
∞
50
5
∞
∞
∞
∞
∞

对图53所示的有向图G，应用Dijkstra算法计算从源顶点v1到其他顶点间最短路径的过程，如表54所示。


表54从源顶点v1到其他顶点的数组dist值和最短路径的求解过程


迭代
S
u
dist［2］
dist［3］
dist［4］
dist［5］
初值
{1}
—
10
∞
25
80
i=1
{1,2}
2
10
50

(v1,v2,v3)
25
80
i=2
{1,2,4}
4
10
45

(v1,v4,v3)
25
75

(v1,v4,v5)
i=3
{1,2,4,3}
3
10
45
25
55

(v1,v4,v3,v5)
i=4
{1,2,4,3,5}
5
10
45
25
55

下面分析Dijkstra算法的运行时间： 代码的核心部分是一个双循环，所以算法时间复杂度是O(n2)。人们可能只希望找到从源点到某一特定终点的最短路径，其实这与求源点到其他所有顶点的最短路径一样复杂，其时间复杂度也是O(n2)。
根据算法5．5中数组prev保存的信息，可以输出相应的最短路径。算法中数组prev［i］记录从源点到顶点i的最短路径上i的前一个顶点。数组prev的初值为0，表示没有前一个结点。
在Dijkstra算法中更新最短路径长度时，只要dist［u］+c［u］［i］＜prev［i］时，就置prev［i］=u。当Dijkstra算法终止时，就可以根据数组prev找到从源点到顶点i的最短路径上每个顶点的前一个顶点，从而找到从源点到顶点i的最短路径。
图53中有向图的数组prev如表55所示。例如，要找出v1到v5的最短路径，根据prev［5］=3得到其前一个结点是3，prev［3］=4得到其前一个结点是4，prev［4］=1得到其前一个结点是1，因此最短路径为(v1,v4,v3,v5)。


表55有向图G的数组prev


结点
1
2
3
4
5
父结点
0
1
4
1
3

获得最短路径的算法如算法5．7所示。
算法5．7根据数组prev计算单源最短路径的算法。

void traceback(int v, int i, int prev［］)

{

cout<<i<<"<--";

i=prev［i］; 

if(i!=v) traceback(v,i,prev);

if(i==v) cout<<i<<endl; 

}

如果要获得源点v1到所有其他顶点的最短路径，使用迭代算法更方便，如算法5．8所示。
算法5．8根据数组prev计算源点v1到所有其他顶点最短路径的迭代算法。

for(int j=2; j<=n; j++)

{

printf("%d",j);

int t = prev［j］;

while (t!=1)

{

printf("<--%d",t);

t=prev［t］;

}

printf("<--1＼n");

}






5．6最小生成树
设G=(V，E)是无向连通带权图，即一个网络。对图中每一条边(u，v)的权为c［u］［v］，表示连通u与v的代价。如果G的子图T是一棵包含G的所有顶点的树，则称T为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树： 

min∑(u，v)∈Tc［u］［v］


如图54所示，显示各条边的权值。粗线的边为最小生成树的边，其各边的权值之和为37。最小生成树不是唯一的，用边(a，h)替代边(b，c)构成另外一棵最小生成树，其各边的权值之和也是37。


图54一个连通图的最小生成树

网络最小生成树在实际中有广泛的应用。例如，在设计通信网络时，用图的顶点表示城市，用边(u，v)的权c［u］［v］表示建立城市u与城市v之间的通信线路所需要的费用，则最小生成树就给出了建立通信网络的最经济的方案。
5．6．1最小生成树的性质
用贪心算法设计策略可以设计出构造最小生成树的有效算法。构造最小生成树的Prim算法和Kruskal算法都是应用贪心算法设计策略的例子。这两个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质。
设G=(V，E)是连通带权图，U是V的真子集。如果(u，v)∈E，且u∈U，v∈V－U，且在所有这样的边中，(u，v)的权c［u］［v］最小，那么一定存在G的一棵最小生成树，它以(u，v)为其中一条边。这个性质有时也称为MST(Minimum Spanning Tree)性质。
可以用反证法证明。假设G的任何一棵最小生成树都不包含(u，v)。设T是连通图的一棵最小生成树，当将边(u，v)加入T中时，由生成树的定义，T中必存在一条包含(u，v)的回路。另一方面，由于T是生成树，则在T上必存在另一条回路(u′，v′)，
其中u′∈U，v′∈V－U，且u′和u之间，


图55含边（u,v）的回路

v′和v之间均有路径相通，如图55所示。
删除边(u′，v′)，便可消除上述回路，同时得到另一棵生成树T′。因为c［u］［v］≤c［u′］［v′］，则T′的代价不高于T，于是T′是包含(u，v)的一棵最小生成树，这与假设矛盾。





5．6．2Prim算法
设G=(V，E)是连通带权图，V＝{v1，v2，…，vn}。
构造G的最小生成树的Prim算法基本思想是： 
首先置S＝{v1}。重复执行下列操作： 只要S是V的真子集，就做如下贪心选择——选取满足条件vi∈S，vj∈V－S，且c［i］［j］是最小的边，将顶点vj添加到S中。这个过程一直进行到S＝V时为止，且选取到的所有边恰好构成G的一棵最小生成树，如算法5．9所示。
算法5．9构成最小生成树的Prim算法描述。

define NUM 1000

void Prim(int n,int c［］［NUM］) 

{

T=;					　　//生成树边的集合

S = {v1};				　　//生成树顶点的集合

while (S!=V)

{

(vi,vj)=vi∈S且vj∈VS的最小权边;

T=T∪{(vi,vj)};

S=S∪{vj}

}

}

算法结束时，T中包含G的n-1条边，S中包含G的n个顶点。
例如，对于图56(a)所示的无向连通带权图，按Prim算法选取边的过程如图56(b)~(f)所示。


图56使用Prim算法构造最小生成树的过程


对于构成最小生成树的Prim算法，还应当考虑如何有效地找出满足条件vi∈S，vj∈V－S，且c［i］［j］是最小的边(vi，vj)。设无向连通带权图的邻接矩阵为数组c，一对顶点(vi，vj)没有直接相连的边时，c［i］［j］=∞。
采用两个数组closest和lowcost实现这个目标。对于每一个vj∈V－S，closest［j］是vj在S中的邻接顶点，它与vj在S中的其他邻接顶点vk比较，有： 

c［j］［closest［j］］≤c［j］［k］，lowcost［j］=c［j］［closest［j］］


在Prim算法的执行过程中，先找出V－S中使lowcost值最小的顶点vj，然后根据数组closest选取边(vj，closest［j］)，最后将vj添加到S中。然后根据vj对closest和lowcost做必要的修改，如算法5．10所示。
算法5．10使用Prim算法构成最小生成树。

#define NUM 1000

#define maxint 10000000		　　//表示∞

//形参n为顶点的个数，数组c为无向连通带权图的邻接矩阵

void  Prim (int n, int c［］［NUM］)

{

int lowcost［NUM］;		　　//类似于算法5.6中的dist数组

int closest［NUM］;		　　//类似于算法5.6中的prev数组

bool s［NUM］ = {false};

//初始化数组

for (int i=1; i<=n; i++)

{

lowcost［i］ = c［1］［i］;

closest［i］ = 1;

s［i］ = false;

}

//从顶点v1开始

s［1］ = true;

//处理其余n-1个顶点

for (int i=1; i<n; i++)

{

//在未处理的结点集中，找最小边权的结点vj

int min = maxint;

int j=1;

for(int k=2; k<=n; k++)

if((lowcost［k］<min) && (!s［k］) )

{

min = lowcost［k］;

j = k;

}

//一条边(vj，closest［j］)

printf("%d %d＼n", closest［j］, j);

//加入结点vj

s［j］ = true;

//根据结点vj，更新数组lowcost和closest

for(int k=2; k<=n; k++)

if((c［j］［k］<lowcost［k］) && (!s［k］))

{

lowcost［k］ = c［j］［k］;

closest［k］ = j;

}

}

}

算法实现源代码： MSTPrim．cpp。
下面分析Prim算法的运行时间： 代码的核心部分是一个双循环，所以算法的时间复杂度是O(n2)。该算法与图中的边数无关，因此适用于计算边稠密的最小生成树。而Kruskal算法恰恰相反，它的计算时间复杂度为O(elog2e)(其中e为图中边的数量)，因此相对于Prim算法，Kruskal算法更适合于计算边稀疏的最小生成树。





5．6．3Kruskal算法
设G=(V，E)是连通带权图，V＝{v1，v2，…，vn}。
Kruskal算法构造G的最小生成树的基本思想是： 首先将G的n个顶点看成n个孤立的连通分量，将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分量。当查看到第i条边(u，v)时，如果端点u和v分别是当前两个不同的连通分量T1和T2中的顶点时，就用边(u，v)将T1和T2连接成一个连通分量，然后继续查看第i+1条边； 如果端点u和v在当前的同一个连通分量中，就直接再查看第i+1条边。这个过程一直进行到只剩下一个连通分量时为止，该连通分量就是G的一棵最小生成树。
例如，图57(b)~(f)所示是按照Kruskal算法构造G的最小生成树的过程。开始时，每个顶点都是一棵树。


图57使用Kruskal算法构造最小生成树的过程


采用抽象数据类型并查集的基本运算，可以很方便地实现Kruskal算法。

（1） 建立边的数据结构。

#define N 1000

struct graph

{

int u,v,cost;			　　//顶点u与顶点v的边权是cost

void set(int a,int b,int w){u=a,v=b,cost=w;}

};

graph d［N*(N+1)/2］;

对于有n个顶点的图，其边的数量e≤n(n+1)/2。
假设有m条边，每条边的描述是｛v，w，edge｝，表示顶点v与顶点w的边权是edge，则可以按如下方式构造边集合d： 

int i;

int v,w,edge;

for (i=0; i<m; i++)

{

scanf("%d%d%d", &v, &w, &edge);

d［i］.set(v,w,edge);

}

（2） 按边权cost的递增顺序排序。
排序因子： 

int cmp(graph x,graph y)

{

if (x.cost<y.cost) return true;

return false;

}

使用C++标准模板库函数排序： 

sort(d, d+m, cmp);

（3） 应用并查集的基本运算，实现Kruskal算法构造G的最小生成树。
并查集是一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
① 查找一个元素所在的集合。
查找一个元素所在的集合，只要找到这个元素所在集合的祖先。
先设置一个数组Father［x］，表示x的“父亲”的编号，即可转换为寻找两个元素的最久远祖先是否相同，可以采用递归实现，如算法5．11所示。
算法5．11查找一个元素所在集合的算法。

int father［N］;

int Find(int x)

{

if (father［x］==-1) return x;

return father［x］ = Find(father［x］);

}

② 合并两个不相交集合。
合并两个不相交集合的方法就是，找到其中一个集合最久远的祖先，将另外一个集合最久远的祖先指向它，如算法5．12所示。
算法5．12合并两个不相交集合的算法。

bool Union(int x, int y)

{

//判断两个元素是否属于同一集合，只要看它们所在集合的祖先是否相同

x = Find(x);

y = Find(y);

//祖先相同，是同一个集合

if (x==y) return false;

//祖先不相同，合并两个集合

if (x>y) father［x］ = y;

if (x<y) father［y］ = x;

return true;

}

③ 应用并查集，实现Kruskal算法构造最小生成树。
因为已经按边权的大小升序排序，所以最先找到满足条件的边就是最小生成树中的一条边，如算法5．13所示。
算法5．13使用Kruskal算法构造最小生成树。

memset(father, -1, sizeof(father));

//最小生成树中边权的和

int sum=0;

//已经找到的边数

int count=0;

//查找每一条边

for(i=0; i<n*(n+1)/2; i++)

{

//找到了一条满足条件的边

if (Union(d［i］.u, d［i］.v))

{

printf("%d %d＼n", d［i］.u, d［i］.v);

sum += d［i］.cost;

++count;

}

if (count==n-1) break;

}

printf("%d＼n",sum); 

算法实现源代码： MST-Kruskal．cpp。
按边权cost递增排序以后，算法5．13使用Kruskal算法构造最小生成树时，count的计数过程如表56所示。


表56使用Kruskal算法构造最小生成树时count的计数过程


i
0
1
2
3
4
5
6
7
8
9
(u,v)
(1,3)
(4,6)
(2,5)
(3,6)
(1,4)
(2,3)
(3,4)
(1,2)
(3,5)
(5,6)
cost
1
2
3
4
5
5
5
6
6
6
count
1
2
3
4

5




对图57所示的图G，算法5．12的输出结果是： 

1 3

4 6

2 5

3 6

2 3

15

前5行刚好与图57(b)~(f)对应，最后一行15是构成的最小生成树的边权和。与图57对应的数组father的值，如表57所示。其中下标表示结点，对应的数值表示该结点的父结点。


表57与图57对应的数组father的值


下标（结点）
1
2
3
4
5
6
父结点
-1
1
1
1
2
4






5．7删数问题
给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法，找出剩下数字组成的新数最小的删数方案。
输入
第1行是1个正整数a，第2行是正整数k。
输出
对于给定的正整数a，编程计算删去k个数字后得到的最小数。
输入样例

178543

4

输出样例

13

【算法分析】
n位数a可表示为x1x2…xixjxk…xn，要删去k位数，使得剩下的数字组成的整数最小。将该问题记为T，其最优解A={xi1xi2xi3…xim}，其中i1＜i2＜…＜im，m=n-k，在删去k个数后剩下的数字按原次序排成的新数，其最优值记为N。
本问题采用贪心算法求解，采用最近下降点优先的贪心策略，即x1＜x2＜…＜xi-1＜xi，如果xi+1＜xi(下降点)，则删去xi，即得到一个新的数且这个数为n-1位中最小的数Nl，可表示为x1x2…xi－1xi+1…xn。显然删去1位数后，原问题T变成了对n-1位数删去k-1个数的新问题T′。新问题和原问题的性质相同，只是问题规模由n减小为n-1，删去的数字个数由k减少为k-1。基于此种删除策略，对新问题T′，选择最近下降点的数继续进行删除，直至删去k个数为止，如算法5．14所示。
算法5．14删数问题的贪心算法实现。

string a;						　　//n位数a

int k;

cin>>a>>k;

//如果k≥n，数字被删完了

if(k >= a.size()) a.erase();

else while(k > 0)

{

//寻找最近下降点

int i;

for(i=0;(i<a.size()-1) && (a［i］ <= a［i+1］); ++i);

a.erase(i,1);				　　//删除xi

k--;

}

//删除前导数字0

while(a.size() > 1 && a［0］ == '0') 

a.erase(0,1);

cout<<a<<endl;

算法实现源代码： DeleteNumber．cpp。
5．7．1问题的贪心选择性质
对问题T删除最近下降点的数xi后得到的N1是n-1位数中最小的数。
根据数的进制特点，对a按权展开后得到： 

a=x1×10n－1+x2×10n－2+…+xi－1×10n－i+1+

xi×10n－i+xi+1×10n－i－1+…+xn


则有： 

N1=x1×10n－2+x2×10n－3+…+xi－1×10n－i+xi+1×10n－i－2+…+xn


假设删去的不是xi而是后面的xi+1，则有： 

N2=x1×10n－2+x2×10n－3+…+xi－1×10n－i+xi×10n－i－1+…+xn


因为有x1＜x2＜…＜xi－1＜xi，且xi+1＜xi(下降点)，则有N1＜N2。
因此删数问题满足贪心选择性质。
5．7．2问题的最优子结构性质
在进行了贪心选择后，原问题T就变成了对N1如何删去k-1个数的问题T′，是原问题的子问题。若A＝(xi，A′)是原问题T的最优解，则A′是子问题T′的最优解，其最优值为NA。
采用反证法证明： 假设A′不是子问题T′的最优解，其子问题的最优解为B′，其最优值记为NB，则有NB＜NA。而根据N的定义可知： N=NA+xi×10n-i，而NB＜NA，因此有NB+xi×10n-i＜NA+xi×10n-i。即存在一个由数a删去1位数后得到的n-1位数比最优值N更小，这与N为问题T的最优值相矛盾，则A′是子问题T′的最优值。
因此，删数问题满足最优子结构性质。





5．8多处最优服务次序问题李洪霞，于仁师，等.用贪心算法求解最优服务次序问题［J］.科技广场，2008（3），1820.
设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti，1≤i≤n，共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。
对于给定的n个顾客需要的服务时间和s的值，编程计算最优服务次序。
输入
第一行有2个正整数n和s，表示有n个顾客且有s处可以提供顾客需要的服务。
接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。
输出
最小平均等待时间，输出保留3位小数。
输入样例

10 2

56 12 1 99 1000 234 33 55 99 812

输出样例

336．000

【算法分析】
假设原问题为T，并已经知道某个最优服务序列，即最优解为A={t1，t2，…，tn}，其中ti为第i个用户需要的服务时间，则每个用户等待时间Ti为： 

T1=t1
T2=t1+t2

Tn=t1+t2+…+tn


那么总的等待时间，即最优值N为： 

N=nt1+(n－1)t2+(n－2)t3+…+2tn－1+tn


由于平均等待时间是n个顾客等待时间的总和除以n，故本题实际上就是求使顾客等待时间的总和最小的服务次序。
设计贪心策略如下： 对服务时间最短的顾客先服务。首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T′。新问题和原问题相同，只是问题规模由n减小为n-1。基于此种选择策略，对新问题T′，在n-1个顾客中选择服务时间最短的先进行服务，如此进行下去，直至所有服务都完成为止，如算法5．15所示。
算法5．15多处最优服务次序问题的贪心算法实现。

//顾客等待的队列为client，提供服务的窗口s个

double greedy(vector<int> client,int s)

{

//服务窗口的顾客等待时间

vector<int> service(s+1,0);

//服务窗口顾客等待时间的总和

vector<int> sum(s+1,0);

//顾客的数量

int n = client.size();

//按顾客的服务时间升序排序

sort(client.begin(),client.end());

//贪心算法的实现

int i=0;					　　//顾客的指针

int j=0;					　　//窗口的指针

while(i < n)

{

service［j］ += client［i］;

sum［j］ += service［j］;

++i,++j;

if(j == s) j = 0;

}

//计算所有窗口服务时间的总和

double t=0;

for(i=0; i<s; ++i) t += sum［i］;

t /= n;

return t;

} 

算法实现源代码： serviceProblem．cpp。
算法5．15中使用Vector创建动态数组，相关知识请参考2．2节。
对于样例数据，计算过程如图58所示。


图58多处最优服务次序问题贪心算法的计算过程


贪心算法实现部分是一重循环，其时间复杂度为O(n)。主要时间花费是前面的排序，排序函数sort()的时间复杂度是O(nlog2n)，所以该算法总的时间复杂度是O(nlog2n)。
5．8．1问题的贪心选择性质
按顾客服务的时间升序排序，获得最优服务序列，即最优解A={t1，t2，…，tn}，其中ti≤ti+1，1≤i≤n-1，此时的最优值为： 

N=nt1+(n－1)t2+(n－2)t3+…+2tn－1+tn


采用反证法证明： 假设t1不是最小的，不妨设t1＞ti(i＞1)。
设另一服务序列B={ti，t2，…，t1，…，tn}，最优值为N′，则： 

N－N′=n×(t1－ti)+(n+1－i)(ti－t1)=(1－i)(ti－t1)＞0

即N＞N′，这与A是最优服务序列相矛盾，故最优服务次序问题满足贪心选择性质。
5．8．2问题的最优子结构性质
在进行了贪心选择后，原问题T就变成了如何安排剩余的n-1个顾客的服务次序的问题T′，是原问题的子问题。若A是原问题T的最优解，则A′={t2，t3，…，tn}是服务次序问题子问题T′的最优解，其最优值为NA。
采用反证法证明： 假设A′不是子问题T′的最优解，其子问题的最优解为B′，相应的最优值为NB，则有NB＜NA。根据N的定义知，NA+t1=N，因此NB+t1＜NA+t1=N，即存在一个比最优值N更短的总等待时间，而这与N为问题T的最优值相矛盾。因此，A′是子问题T′的最优值。
从以上贪心选择及最优子结构性质的证明，可知最优服务次序问题用贪心算法可求得最优解。平均等待时间即为N/n。





5．9ZOJ1012Mainframe
【问题描述】
多纳(Ronald)先生是ACM(Agent on Computing of Mathematics，计算数学代理商)大型计算机的管理员。该代理商为一些公司承担在大型计算机上的计算工作，完成工作后获得报酬，因此大型计算机对这个代理商来说太重要了。多纳先生需要为这些在大型计算机上运行的作业安排顺序。一旦要运行某项作业，他就要检查运行该作业所需要的空闲资源。如果空闲资源足够的话，他就为该作业分配这些资源； 否则就将该作业挂起，直至有足够的资源投入运行。
刚开始他并不熟悉这项工作，把事情搞得很乱。日积月累，他就胜任这项工作了，而且他还总结了如下一套规则： 
(1) 大型计算机有M个CPU和N大小的内存空间可供分配。
(2) 对等待运行的作业有一个等待队列。可以假定这个队列足够长，能够存放所有等待运行的作业。
(3) 假定作业Ji需要Ai个CPU和Bi的内存空间，在时间Ti到达等待队列，需要在时间Ui之前完成。成功运行后，代理商可以获得Vi(美元)的报酬； 如果能在规定的时间之前完成，则每小时还可以额外获得Wi(美元)的奖金； 如果工期拖延，则每小时赔偿Xi(美元)。例如，假定一项作业的报酬是10美元，时限8小时，每拖欠1小时罚2美元。如果该作业在10小时完成，则代理商可以获得报酬： 10－(10－8)×2=6美元。
(4) 当一项作业开始后，就独占了分配给它的CPU和内存空间，不能同时再分配给其他的作业。当该作业运行结束后，这些资源被释放。如果资源足够多，同时可以运行多项作业。
(5) 为了最大限度地发挥大型计算机的计算能力，每项作业在开始运行后刚好1小时就完成。你可以假定每项作业的运行时间就是1小时。
(6) 没有作业运行时，机器空闲，一直到一项作业进入作业等待队列。
(7) 如果有多项作业进入作业等待队列，则报酬高的作业优先。可以假定这些作业的报酬都不相等(Vi≠Vj)。
(8) 如果某项作业的空闲CPU或内存空间不能满足，它就要被挂起1小时，也不占用任何资源。一小时后，再次为该作业检查资源，而不需要考虑等待队列里的其他作业。如果资源仍不满足要求，那就继续挂起1小时，把资源分配给其他在等待队列里的作业； 否则，该作业将独占CPU和存储空间并投入运行。
(9) 当多项作业挂起时，采取先来先服务的原则。
使用这些规则，多纳先生把事情安排得井井有条。现在除了日常公务外，代理商要求他根据作业列表计算收入。给定某个时间F，计算出已经完成的作业和应该被完成的作业。对作业Ji，如果它的时限Ui＞F并且仍未完成，就不需要统计收入。对已经完成的作业或Ui≤F的作业都要统计。如果工作没有完成，它不会给代理商带来报酬，但到这个时间F为止的罚款仍要计算。
他不会程序设计，又不想手工做，现在很不安。你可以帮助他解决这个问题吗？
输入
有多组测试例。每个测试例描述大型计算机的资源和作业列表，第一行是整数F(0≤F≤10000)，表示时限； 接下来的一行是三个整数M，N和L(M，N，L≥0)，M是机器CPU的数量，N是存储空间的大小，L是作业等待队列中作业的数量。最多有10000项作业。
后面的L行是作业的信息。描述作业Ji的数据是7个整数： Ai，Bi，Ti，Ui，Vi，Wi和Xi。Ai和Bi(Ai，Bi≥0)指出了该作业对CPU和内存的需求； Ti和Ui表示作业的到达时间和时限(0≤Ti≤Ui)； Vi，Wi，Xi分别是工作的报酬、奖励和罚款(Vi，Wi，Xi≥0)。
一个空的测试例(F＝0)表示输入结束，该测试例无须处理。
输出
根据作业列表算总收入。对每个测试例，都输出测试例编号，一个冒号，一个空格，然后是收入。
测试例之间有一个空行。
注意： 对尚未投入运行的且时限超过F的作业，不必统计。
输入样例

10

4 256 3

1 16 2 3 10 5 6

2 128 2 4 30 10 5

2 128 2 4 20 10 5

0

输出样例

Case 1: 74

题目来源
Asia 2001,Shanghai (Mainland China)
【算法分析】
在进行资源分配时，运用贪心策略能够获得很好的效率。
1． 样例分析
时限F＝10； 
CPU数量M＝4，存储空间N＝256，作业数量L＝3。
3个作业的参数如表58所示。


表58样例作业的参数


作业编号
A

(CPU)
B

(内存空间) 
T

(到达时间) 
U

(时限) 
V

(报酬) 
W

(奖励) 
X

(罚款) 
0
1
16
2
3
10
5
6
1
2
128
2
4
30
10
5
2
2
128
2
4
20
10
5

按规则（9）排序： 先来先服务的原则，根据到达时间排序； 而到达时间是一样的，按规则（7）排序： 报酬高的作业优先。排序后的结果如表59所示。


表59样例作业的排序结果


作业编号
A

(CPU)
B

(内存空间) 
T

(到达时间) 
U

(时限) 
V

(报酬) 
W

(奖励) 
X

(罚款) 
1
2
128
2
4
30
10
5
2
2
128
2
4
20
10
5
0
1
16
2
3
10
5
6

前面两项作业，在时间2到达，刚好有4个CPU和256个存储空间可用，立即投入运行，而且在时限4之前结束，既有报酬又有奖金(提前1小时)。
作业1收益： 30+10。
作业2收益： 20+10。
这两项作业在时间3运行结束，接着运行作业3，至时间4结束，晚点时间1小时： 
作业3收益： 10-6＝4。
总收益是74。
2． 数据结构
对每项作业，使用一个结构体表示其7个参数： 

#define Max 10001

struct Node{

int a,b;		　　//分别为CPU和内存空间

int t,u;		　　//分别为到达时间和时限

int v,w,x;		　　//分别为报酬、奖励和罚款

};

对所有作业，使用数组Job表示： 

Node Job［Max］;

作业完成的状态保存到数组Finished中： 

bool Finished［Max］;

3． 作业排序
应用sort()函数对作业进行排序： 

sort(Job, Job+L, cmp);

其中比较因子cmp()函数的实现： 

bool cmp(Node a , Node b) 

{ 

//根据到达时间优先排序(升序)

if (a.t!=b.t) return a.t<b.t; 

//到达时间相等时，按报酬数量降序排序

else return a.v>b.v; 

}

4． 报酬的计算
排序之后就可以实现贪心策略了。
在统计时限F之前到达的所有作业，能够运行的就计酬，不能运行的就罚款。
按照排好的顺序，依次将作业投入运行，资源足够的就投入运行，资源不够的作业就等待下一个小时。由于所有作业都只需要运行1小时，因此在每小时开始时，资源的数量都是原始数量，如算法5．16所示。
算法5．16大型计算机作业调度问题的贪心算法实现。

int i,j;

int iCase = 0;				　　//测试例编号

int F;							　　//统计时限

while(scanf("%d",&F) && F)

{

iCase++; 

int Profit = 0;			　　//报酬

memset(Finished, 0, sizeof(Finished));

//分别表示CPU、内存空间和作业的数量

int M,N,L;

scanf("%d%d%d",&M, &N, &L);

for(i = 0; i<L; i++)

scanf("%d%d%d%d%d%d%d", &Job［i］.a,

&Job［i］.b,	&Job［i］.t, &Job［i］.u,

&Job［i］.v, &Job［i］.w, &Job［i］.x);

//按函数cmp()的要求排序

sort(Job, Job+L, cmp);

int count = 0;			　　//统计完成作业的数量

//在统计时限内完成L个作业

for(i = 0; i<F && count < L; i++)	

{　　//每一小时开始时，所有资源都是空闲的

int cpu = M;

int memory = N; 

//对所有的作业搜索一遍

for(j = 0; j<L; j++)

{

//该时刻作业还没有到达

if(Job［j］.t>i) break;

//如果作业还没有运行，并且资源足够

if(!Finished［j］ && cpu>=Job［j］.a && memory>=Job［j］.b)

{

cpu -= Job［j］.a;			　　//占有资源

memory -= Job［j］.b;

Finished［j］ = 1;			　　//设置完成标志

Profit += Job［j］.v;		　　//计算报酬

if(i+1 <= Job［j］.u)		　　//计算奖金

Profit += (Job［j］.u-i-1)*Job［j］.w;

else						　　//计算罚款

Profit -= (i+1-Job［j］.u)*Job［j］.x;

count++;					　　//完成了一项作业

}

}

}

//在统计时限F之前到达的作业，没有运行的就要罚款

for(i = 0; i<L; i++)

if(!Finished［i］&&Job［i］.u <= F)

Profit -= (F-Job［i］.u)*Job［i］.x;

printf("Case %d: %d＼n＼n", iCase, Profit);

}

算法实现源代码： zju1012．cpp。





5．10ZOJ1025Wooden Sticks
【问题描述】
现有n根木棒，已知它们的长度和质量。要用一部木工机一根一根地加工这些木棒。该机器在加工过程中需要一定的准备时间，是用于清洗机器，调整工具和模板的。
木工机需要的准备时间如下： 
(1) 第一根木棒需要1min的准备时间； 
(2) 在加工了一根长为l，重为w的木棒之后，接着加工一根长为l′(l≤l′)，重为 w′(w≤w′)的木棒是不需要任何准备时间的，否则需要1min的准备时间。
给定n根木棒，你要找到最少的准备时间。例如现在有长和重分别为(4，9)，(5，2)，(2，1)，(3，5)和(1，4)的5根木棒，那么所需准备时间最少为2min，顺序为(1，4)，(3，5)，(4，9)，(2，1)，(5，2)。
输入
输入有多组测试例。输入数据的第一行是测试例的个数T。
每个测试例两行： 第一行是一个整数n(1≤n≤5000)，表示有多少根木棒； 第二行包括n×2个整数，表示l1，w1，l2，w2，l3，w3，…，ln，wn，全部不大于10000，其中li和wi表示第i根木棒的长度和质量。数据由一个或多个空格分隔。
输出
输出是以分钟为单位的最少准备时间，一行一个。
输入样例

3

5

4 9 5 2 2 1 3 5 1 4

3

2 2 1 1 2 2

3

1 3 2 2 3 1

输出样例

2

1

3

题目来源
Asia 2001, Taejon (South Korea)
【算法分析】
对这种资源调度问题，贪心算法能够获得很好的效率。
但本题仅仅使用贪心算法是不够的，排序之后还要使用动态规划的算法，所以在网上会有把本题归类为贪心算法和动态规划算法。
1． 数据结构
采用结构体表示木棒的信息： 

#define maxN 5001

struct stick 

{ 

int l;				　　//木棒的长度

int w;				　　//木棒的质量

};

stick data［maxN］;		　　//存放所有木棒

2． 按木棒的长度使用贪心算法
利用C++的标准模板库函数sort()实现排序： 

sort(data, data+n, cmp);

排序函数cmp()的实现： 

int cmp(stick a, stick b) 

{ 

//长度相等时，按质量排序

if(a.l == b.l) 

return a.w < b.w; 

//优先按长度排序

else if (a.l < b.l) return true;

return false;

}

对于样例数据1，排序之后的结果如表510所示。



表510样例数据1排序之后的结果


下标
0
1
2
3
4
长度l
1
2
3
4
5
质量w
4
1
5
9
2
数组b
1
2
1
1
2

3． 使用动态规划的方法，计算质量w的单调递增子序列的个数
从表510直观地看到，对质量w，4，5和9是一组，1和2是一组，所以答案是2。
用数组b记录质量w的分组序号，在表510中，4，5和9的组序号是1，1和2的组序号是2。则a［i］．w(0≤i＜n)的递增子序列的分组个数为： max0≤i<n{b［i］}。
b［i］满足最优子结构性质，可以递归地定义为： 

b［0］＝1； 
b［i］ ＝max0≤i<n

a［i］.w<a［j］.w{b［j］}+1(0≤j＜i)


该算法统计质量w的单调递增子序列的个数，而对每个递增子序列，并不一定是最长的。例如数据： (3170)，(4155)，(5239)，(6300)，(7240)，(8241)，(9369)，数组b的值为(1，2，1，1，2，2，1)，对应数组b为1的w序列为(170，239，300，369)，而最长单调递增子序列是(170，239，240，241，369)。程序实现如算法5．17所示。
算法5．17计算质量w的单调递增子序列个数的动态规划实现。

//形参n是木棒的数量，stick是木棒参数的数组

int DP(int n, stick a［］) 

{

//数组b表示木棒分组的序号

int b［maxN］; 

memset(b, 0, sizeof(b));

int i, j, k;

b［0］=1;

for (i=1; i<n; i++) 

{

//计算第i个木棒的分组序号

k=0;

//在i的前面，比a［i］大的单元中，找b的最大值，然后k+1

for (j=0; j<i; j++) 

if (a［i］.w<a［j］.w && k<b［j］) k=b［j］;

b［i］=k+1;

}

//查找最大的分组序号(数组b中的最大值)

int max=0;

for (i=0; i<n; i++)

if (b［i］>max) max=b［i］;

return max;

}

算法实现源代码： zju1025sort．cpp。
既然是统计质量w的单调递增子序列的个数，则可以应用活动安排问题的算法，找到第一个分组； 对剩下的数据继续应用活动安排问题的算法，找到第二个分组； 以此类推，直到所有的质量w都已经安排。最后分组的数量count就是答案。
算法实现源代码： zju1025greedy．cpp。





5．11ZOJ1029Moving Tables
【问题描述】
著名的ACM(Advanced Computer Maker)公司租用了一层有400个房间的办公楼，结构如图59所示。


房间1房间3房间5…房间397房间399
走廊
房间2房间4房间6…房间398房间400


图59ACM公司办公楼示意图

这层楼沿着走廊南北向的两边各有200个房间。最近，公司要做一次装修，需要在各个办公室之间搬运办公桌。由于走廊狭窄，办公桌都很大，走廊里一次只能通过一张办公桌。必须制订计划提高搬运效率。经理制订如下计划： 一张办公桌从一个房间移到另一个房间最多用10分钟。当从房间i移动一张办公桌到房间j，两个办公室之间的走廊都会被占用。所以，每10分钟内，只要不是同一段走廊，都可以在房间之间移动办公桌。为了说得更清楚一些，经理举例说明哪些情况可以同时移动，哪些情况不能同时移动，如表511所示。


表511办公桌移动的状态


分类
移动办公桌
理由
可行的
(房间30到50)和(房间60到90)
走廊不重叠
(房间11到12)和(房间14到13)
走廊不重叠
不可行的
(房间20到40)和(房间31到80)
房间31到房间40的走廊重叠
(房间1到4)和(房间3到6)
房间3前面的走廊重叠
(房间2到8)和(房间7到10)
房间7前面的走廊重叠

每个房间，只有一张办公桌进出。现在，经理想找到一种方案，使移动桌子的事情尽快完成。请编写程序解决经理的难题。
输入
输入数据有T组测试例，在第一行给出测试例个数T。
每个测试例的第一行是一个整数N(1≤N≤200)，表示要搬运办公桌的次数。接下来的N行，每行都有两个正整数s和t，表示一张桌子是从房间号码s移到房间号码t。
有多组输入数据，输入第一行为一个表示输入数据总数的整数N，然后是N组输入数据。
输出
每组输入都有一行的输出数据，为一整数T，表示完成任务所花费的最小时间。
输入样例

3

423

10 201 310100

30 402 2002080

50 603050

70 80

输出样例

10

20

30

题目来源
Asia 2001,Taejon (South Korea)
【算法分析】
在经理给出的说明表格中，已经明确地描述了算法： 
 (从房间30到50)和(从房间60到90)是允许的，因为没有占用公共的走廊； 
 (从房间20到40)和(从房间31到80)是不允许的，因为要占用公共的走廊。
我们将每个房间之间的走廊作为一个统计单位，当所有的办公桌都搬运完成之后，看看这段走廊到底需要占用多少次？然后统计所有的走廊被占用的最大值max，这个值就是要单独安排的搬运次数，乘以10就是总的搬运时间。
房间与走廊的映射关系，如表512所示。


表512房间与走廊的映射关系


房间编号
1，2
3，4
5，6
7，8
…
397，398
399，400
表示走廊的数组下标
0
1
2
3
…
198
199

该算法应该属于贪心算法，因为它尽可能使搬运办公桌同时进行，以便使单独安排的搬运次数最少。程序实现如算法5．18所示。
算法5．18ACM公司搬运办公桌的贪心算法实现。

int i, j;

//每个房间之间一个走廊，一共有200个公共走廊

int move［200］;

int N;							　　//搬运次数

//每次搬运的起点和终点

int from, to;

scanf("%d", &N); 

memset(move, 0, sizeof(move));

for(i = 0; i < N; i++)

{

scanf("%d%d", &from, &to);

//将房间号映射为走廊号

from = (from - 1)/2;

to = (to - 1)/2;

//确保from<to

if(from > to) swap(from, to);

}

//占用走廊情况

for(j = from; j <= to; j++)

move［j］++;

}

//所有的走廊被占用的最大值

int max = 0;

for(i = 0; i < 200; i++)

if(move［i］ > max) max = move［i］;

printf("%d＼n", max * 10);

算法实现源代码： zju1029．cpp。

例如样例1： (10，20)，(30，40)，(50，60)和(70，80)，四次搬运都不占用公共的走廊，所以可以同时进行，一次搬运成功。





5．12ZOJ1076Gene Assembly
【问题描述】
随着大量的基因组DNA序列数据被获得，其对于了解基因越来越重要(基因组DNA的一部分是负责蛋白质合成的)。众所周知，在基因组序列中，由于存在垃圾的DNA中断基因的编码区，真核生物(相对于原核生物)的基因链更加复杂。也就是说，一个基因被分成几个编码片段(称为外显子)。虽然在蛋白质的合成过程中，外显子的顺序是固定的，但是外显子的数量和长度可以是任意的。
大多数基因识别算法分为两步： 第一步，寻找可能的外显子； 第二步，通过寻找一条拥有尽可能多的外显子的基因链，尽可能大地拼接一个基因。这条链必须遵循外显子出现在基因组序列中的顺序。外显子i在外显子j的前面的条件是i的末尾必须在j开头的前面。
本题的目标： 给定一组可能的外显子，找出一条拥有尽可能多的外显子链，拼接成一个基因。
输入
给出几组输入实例。每个实例的开头是基因组序列中可能的外显子数n(0＜n＜1000)。接着的n行，每行是一对整数，表示外显子在基因组序列中的起始和结束位置。假设基因组序列最长为50000。当一行是0时，表示输入结束。
输出
对于每个实例，找出尽可能多的外显子链，输出链中的外显子，并占一行。假如有多条链，但外显子数相同，那么可以输出其中任意一条。
输入样例

630

340 500705 773

220 470124 337

100 300453 665

880 943

525 556

612 776

输出样例

3 1 5 6 4

2 3 1

题目来源
South America 2001
【算法分析】
虽然本题有很多人使用动态规划算法，但最简单的算法是贪心算法，相当于只有一个资源的活动安排问题。其算法的详细描述，请读者阅读本书5．1节。
1． 数据结构
外显子数为n，外显子的结构体表示： 

struct gene {

int start, end, pos;	　　//起始和结束位置，序号

}seq［1000］;				　　//存放外显子的数组

2． 排序算法
按外显子的结束位置升序，排序因子： 

bool cmp(gene a, gene b)

{

if (a.end<b.end) return true;

return false;

}

程序实现如算法5．19所示。
算法5．19基因拼接问题的贪心算法实现。

while(scanf("%d", &n) && n)

{

//读取外显子

for(int i = 0; i < n; i++) 

{

seq［i］.pos = i + 1;

scanf("%d%d", &seq［i］.start, &seq［i］.end);

}

//按外显子的结束位置升序排序

sort(seq, seq+n, cmp);

//贪心算法的实现，第一个总是有效的

int preEnd = seq［0］.end;

printf("%d", seq［0］.pos);

for(int i = 0; i < n; i++)

//第i个显子的起始位置必须大于前一个选中的显子的结束位置

if(seq［i］.start > preEnd)

{

preEnd = seq［i］.end;

printf("%d", seq［i］.pos);

}

printf("＼n");

}

算法实现源代码： zju1076sort．cpp。对于样例数据1，计算结果如表513所示。


表513样例数据1的计算结果


原始顺序
1
2
3
4
5
6
340 500
220 470
100 300
880 943
525 556
612 776
拼接之后的顺序
3
1
5
6
4

100 300
340 500
525 556
612 776
880 943








5．13ZOJ1161Gone Fishing
【问题描述】
约翰想要去钓鱼。他有h(1≤h≤16)个小时的时间，在该地区有n(2≤n≤25)个湖，这些湖刚好分布在一条路线上，该路线是单向的。约翰从湖1出发，他可以在任一个湖结束钓鱼。但他只能从一个湖到达另一个与之相邻的湖，而且不必每个湖都停留。假设湖i(i＝1，…，n-1)，以5分钟为单位，从湖i到湖i+1需要的时间用ti(0＜ti≤192)表示。例如t3＝4，是指从湖3到湖4需要花20分钟时间。
为了制订钓鱼计划，约翰收集了一些湖的信息。已知在最初5分钟，湖i预计钓到鱼的数量为fi(fi≥0)。以后每隔5分钟，预计钓到鱼的数量将以常数di(di≥0)递减。如果某个时段预计钓到鱼的数量小于或等于di，那么在下一时段将钓不到鱼。为简单起见，假设没有其他的钓鱼者影响约翰的钓鱼数量。
编写一个程序，帮助约翰制订钓鱼旅行的计划，以便他尽可能多地钓到鱼。在每个湖上花费的时间必须是5的倍数。
本题可以包含多组测试例。
多组测试例的第一行是一个整数N，然后是一个空行，接着是N个输入数据块。每个数据块的格式都在问题描述中给出。每个数据块之间都有一个空行。
输出格式包括N个输出数据块，每个输出数据块之间都有一个空行。
输入
输入有多组测试例。对每组测试例，第一行都是n，接下来一行是h。下面一行是n个整数fi(1≤i≤n)，然后是一行n个整数di(1≤i≤n)，最后一行是n-1个整数ti(1≤i≤n-1)。当n＝0时，输入结束。
输出
对每个测试例，输出在每个湖上花费的时间，用逗号分隔，这是约翰要实现钓到最多的鱼的计划(必须使整个计划在同一行输出，即使超过80个字符)。接下来一行是钓到的鱼的数量。如果存在很多方案，尽可能选择在湖1钓鱼所耗费的时间，即使有些时段没有钓到鱼； 如果还是无法区分，那就尽可能选择在湖2钓鱼所耗费的时间，以此类推。测试例之间有一个空行。
输入样例

144

44

210 15 20 1710 15 50 30

10 3 4 30 3 4 3

10 11 2 31 2 3

2 50

2

输出样例

45, 5

Number of fish expected: 31

240, 0, 0, 0

Number of fish expected: 480

115, 10, 50, 35

Number of fish expected: 724

题目来源
East Central North America 1999;Pacific Northwest 1999
【算法分析】
本题在刘汝佳的《算法艺术与信息学竞赛》第一章“算法与数据结构”中有描述。在网站上也有很多资料，基本上都是使用贪心算法。
1． 数据结构
每个湖预计钓到鱼的数量，定义为数组： 

#define NUM 30 

int f［NUM］;

每个湖预计钓到鱼的数量的递减值，定义为数组： 

int d［NUM］;

相邻湖之间的旅行时间，定义为数组： 

int t［NUM］;

钓鱼计划，定义为数组： 

int plan［NUM］;

湖的个数n，用于钓鱼的时间h，尽可能多地钓鱼数量best。
2． 搜索，在任意一个湖结束钓鱼时的最优钓鱼计划
首先把用于钓鱼的时间h，由小时转换为以5分钟为单位的时间： 

h=h×60/5


这样把钓5分钟鱼的时间称为钓一次鱼。由于约翰从湖1出发，可以在任一个湖结束钓鱼，要得到最优解，就需要进行搜索。
设花费在路程上的时间为： 

inttime = 0;

假设约翰在第m个湖结束钓鱼，因为路程是单向的，所以路程上的时间： 

time=∑mi=1t［i］，并且满足h-time＞0。


于是展开搜索： 

for (i = 1; i <= n && h-time; ++i)

{ 

greedy(i, h - time); 

time += t［i］; 

} 

其中函数greedy()为： 

void greedy(int pos, int time);

约翰在第pos个湖结束钓鱼，用于钓鱼的时间是time(不含路程)，即钓鱼time次。该函数采用贪心算法构造约翰的钓鱼计划。可以认为约翰能从一个湖“瞬间转移”到另一个湖，即在任意一个时刻都可以从湖1到湖pos中任选一个钓一次鱼。
3． 采用贪心策略，每次选择鱼最多的湖钓一次鱼
对于每个湖来说，由于在任何时候鱼的数目只和约翰在该湖里钓鱼的次数有关，和钓鱼的总次数无关，所以这个策略是最优的。一共可以钓鱼time次，每次在n个湖中选择鱼最多的一个湖钓鱼，程序实现如算法5．20所示。
算法5．20选择鱼最多的湖钓鱼的贪心算法实现。

//从湖1起到湖pos止，花费时间time(不含路程)的钓鱼计划

void greedy(int pos, int time)

{ 

//时间已经用完

if (time <= 0) return;

int i, j;

int fish［MAXN］;

int p［MAXN］;

int t = 0; 

for (i = 0; i < pos; ++i) 

fish［i］ = f［i］; 

memset(p, 0, sizeof(p)); 

//在时间time内，选择鱼最多的湖钓鱼；如果鱼都没有了，就把时间放在湖1上

for (i = 0; i < time; ++i)

{ 

//鱼最多的湖中，鱼的数量

int max = 0;

//鱼最多的湖的编号

int id = -1;

//查找鱼最多的湖中，鱼的数量和湖的编号

for (j = 0; j < pos; ++j)

if (fish［j］ > max){ 

max = fish［j］; 

id = j; 

} 

//找到了，进行钓鱼处理

if (id != -1)

{

++p［id］; 

fish［id］ -= d［id］; 

t += max; 

}

//没有找到(从湖1起到湖pos全部钓完了)，就把时间放在湖1上

else ++p［0］; 

} 

//处理最优方案

if (t > best)

{ 

best = t; 						　　//最优值

memset(plan, 0, sizeof(plan));

for (i = 0; i < pos; ++i) 	　　//最优解

plan［i］ = p［i］; 

}

}

输出钓鱼计划时，再把5乘回去，就变成实际的钓鱼时间(分钟)： 

for (i=0; i<n-1; ++i) 

printf("%d, ", plan［i］ * 5); 

printf("%d＼n", plan［n-1］ * 5); 

printf("Number of fish expected: %d＼n", best);

算法实现源代码： zju1161．c。





5．14ZOJ1171Sorting the Photos
【问题描述】
假如你有n(1≤n≤105)张照片。有些照片正面朝上，而有些是反面朝上。你的任务是排序，使所有的照片朝向一致。需要做的操作是，从一堆照片中把需要翻转的照片挑出来放成一堆，然后把这堆照片翻转过来，放回到原来的那堆照片上。
编写程序： 采用上述的操作方法完成排序，计算最少的操作次数。
本题包含多组测试例。
多组测试例的第一行都是一个整数N，然后是一个空行，接着是N个输入数据块。每个数据块的格式都在问题描述中给出。每个数据块之间都有一个空行。
输出格式包括N个输出数据块，每个输出数据块之间都有一个空行。
输入
输入的第一行只有一个数字。然后是一组字符，这些字符在不同的行，用/或者空格隔开，字符D表示正面向下，U表示正面朝上。
输出
一个整数，即给照片排序所需最少的翻转操作次数。
输入样例

1

5

UU D

UU

输出样例

2

【算法分析】
由于照片多达105张，回溯算法肯定是太慢了。必须找到一种翻转照片的方法，方法本身就是最优的。这里面有一个技巧，从一堆照片中取照片是不计操作次数的，只有翻转时才计算操作次数。因此我们就逐张照片比较，如遇到照片不同时就翻转一次，再用当前照片的朝向接着比较。例如，样例数据UUDUU，操作步骤如下： 
(1) 先将UU放在一边，遇到D，将UU翻转，放到原来的堆上面，成为DDDUU； 
(2) 将DDD放在一边，遇到U，将DDD翻转，放到原来的堆上面，成为UUUUU。
朝向就变成一样的了，操作次数是2。
编程时，还可以简化，从第一张照片开始与下一张照片比较，如果遇到照片朝向不同，则翻转次数加1，再用不同的那张照片朝向接着与下一张比较，直到结束。
程序实现如算法5．21所示。
算法5．21翻转照片的贪心算法实现。

int i;

int n;							　　//照片的张数

char p［100000］;				　　//存放照片

int N;							　　//数据块的数量

scanf("%d", &N);

while(N--)

{  

scanf("%d", &n);

for(i = 0; i < n; )

{

scanf("%c", p + i);	

//跳过分隔符

if(p［i］ == 'U' || p［i］ == 'D') i++;

}

//最少的翻转操作次数

int ans = 0;

//比较位置

int pos = 0;

//逐张照片比较，如遇到不同则ans+1，再用当前照片的朝向接着比较

for(i = 1; i < n; i++)

if(p［i］ != p［pos］)

{

pos = i;

ans++;

}

printf("%d＼n", ans);

if(N) putchar('＼n'); 

}

算法实现源代码： zju1171．c。
为什么这种方法能够得到最优解呢？实际上这种方法采用了贪心策略，不仅每一步是最优的，而且整体也是最优的，即具有最优子结构性质。
基于这种算法，代码还可以进一步简化： 取消数组，在读取数据的时候就进行比较。
算法实现源代码： zju1171noArray．c。






5．15ZOJ2109FatMouse Trade
FatMouse准备了M磅的猫粮，打算与看守仓库的猫交换食品，仓库里存放着它喜爱的食物JavaBean。
仓库有n个库房，库房i存放J［i］磅JavaBean，需要F［i］磅猫粮予以交换。FatMouse不需要交换库房里所有的JavaBean，可以按比例交换。如果它支付F［i］×a%磅的猫粮，就可以换取J［i］×a%磅的JavaBean，其中a是实数。
现在明确编程任务： FatMouse最多能换取多少JavaBean。
输入
输入包含多组测试例。
对每个测试例，第一行是两个非负整数M和N。接下来N行，每行两个非负整数J［i］和F［i］。最后一个测试例是两个-1，不需要处理。所有的整数都不超过1000。
输出
对每个测试例，都输出一行： 是一个实数，精确到小数点后3位，表示FatMouse最多能换取的JavaBean数量。
输入样例

5 320 3

7 225 18

4 324 15

5 215 10

-1 -1

输出样例

13．333

31．500

【算法分析】
FatMouse用M磅猫粮与猫换取它喜爱的食物JavaBean。JavaBean存储在一个仓库的N个库房中，而且每个库房的JavaBean所需要的猫粮代价是不一样的。以样例数据1为例，其代表的状态如表514所示。


表514样例数据1所表示的状态


库房号
1
2
3
存储的JavaBean
7
4
5
所需要的猫粮代价
2
3
2

当FatMouse剩余的猫粮不够换取整个库房的JavaBean时，可以按比例换取。题目要求猫能够换取尽可能多的JavaBean。
1． 为了使猫能够换取尽可能多的猫粮，就要计算出每个库房的性价比
定义数据结构： 

#define N  1005

struct trade

{

int java;			　　//库房中的JavaBean

int food; 			　　//换取该库房JavaBean所需要的猫粮

double ratio;		　　//用猫粮换取JavaBean时的性价比

}a［N］;

对样例数据1，猫粮换取JavaBean的性价比如表515所示。


表515样例数据1猫粮换取JavaBean的性价比


存储的JavaBean
7
4
5
所需要的猫粮代价
2
3
2
性价比
3．5
1．3333
2．5

2． 按性价比排序
应该从性价比最好的库房换取，这就需要按性价比进行降序排序。排序因子： 

bool cmp(const info& a, const info& b)

{

if (a.ratio>b.ratio) return true;

return false;

}

使用C++的标准模板库函数排序： 

sort(a, a+n, cmp); 

3． 应用贪心算法，用猫粮换取JavaBean
当猫粮足够多时，按库房的性价比由高到低换取； 
当猫粮的量不足以换取整个库房的JavaBean时，则按比例换取。
程序实现如算法5．22所示。
算法5．22FatMouse用猫粮换取JavaBean的贪心算法实现。

double beans = 0;				　　//换取到的JavaBean

int catfood = 0;				　　//花费的猫粮

//采用贪心算法换取猫粮

//m-catfood是当前FatMouse还剩下的猫粮

for (i=0; i<n && m-catfood>=a［i］.food; i++)

{

beans += a［i］.java;

catfood += a［i］.food;

}

//剩下的猫粮不够换取一个库房的JavaBean，则按比例换取JavaBean

if (i<n)

beans += (m - catfood) * a［i］.ratio;

printf("%.3lf＼n", beans);

算法实现源代码： zju2109．cpp。
上机练习题
浙江大学在线题库(由于ZOJ题目很多，这里只列出了部分题目，仅供参考)： 




1117Entropy

1161Gone Fishing

1200Mining

1239Hanoi Tower Troubles Again!

1307Packets

1360Radar Installation

1375PassMuraille

1409Communication System

1543Stripies

2049Advertisement

2091Mean of Subsequence

2229Ride to School

2256Mincost

2315New Year Bonus Grant

2343Robbers

2354Elevator Stopping Plan

2378Evil Straw Warts Live

2397Tian JiThe Horse Racing 2425Inversion

2488Rotten Ropes

2510Concentric Rings

2521LED Display

2536Best Balance

2541Goods Transportation

2702Unrhymable Rhymes

2710Two Pipelines

2833Friendship

2921Stock

3116Loan Scheduling

3197Google Book

3301Make Pair

3410Laytons Escape

3424Rescue

3433Gu Jian Qi Tan

3508The War


北京大学在线题库(由于POJ题目很多，这里只列出了部分题目，仅供参考)： 




1017Packets

1042Gone Fishing

1062昂贵的聘礼

1065Wooden Sticks

1125Stockbroker Grapevine

1230PassMuraille

1258AgriNet

1323Game Prediction

1328Radar Installation

1456Supermarket

1679The Unique MST

1716Integer Intervals

1755Triathlon

1784Huffmans Greed

1789Truck History

1797Heavy Transportation

1860Currency Exchange

1861Network

1862Stripies

1922Ride to School

2054Color a Tree

2209The King2240Arbitrage

2253Frogger

2287Tian JiThe Horse Racing

2313Sequence

2325Persistent Numbers

2370Democracy in danger

2393Yogurt factory

2395Out of Hay

2431Expedition

2485Highways

2709Painter

3026Borg Maze

3228Gold Transportation

3253Fence Repair

3259Wormholes

3262Protecting the Flowers

3522Slim Span

3544Journey with Pigs

3614Sunscreen

3617Best Cow Line

3625Building Roads

3723Conscription