【关键字】 贪心策略   特点   理论基础   应用

【摘要】

本文着重探讨的是贪心策略的数学模型、理论基础（“矩形胚”结构）和贪心策略的特点。（贪心选择性质和局部最优解）介绍了3种体现“贪心”思想的图形算法：Dijkstra算法、Prim算法和Kruskal算法，并着重给出了近几年来在各级各类程序设计竞赛中出现的一些题目。     

【正文】                                                                                                                          

一、  引  论

信息，人类社会发展的重要标志。人类对信息的记载，可以追溯到原始社会。在漫长的人类社会发展过程中，伴随着科学技术的发展，人类对客观世界的认识不断加深，现实世界的信息量急剧增大。为了满足人们对大数据量信息处理的渴望，1946年世界上第一台电子数字计算机ENIAC应运而生。在此后的半个世纪中，为解决各种实际问题，计算机算法学得到了飞速的发展。线形规划、动态规划等一系列运筹学模型纷纷运用到计算机算法学中，解决了诸如经济决策等一系列现实问题。在众多的计算机解题策略中，贪心策略可以算得上是最接近人们日常思维的一种解题策略，正基于此，贪心策略在各级各类信息学竞赛、尤其在对NPC类问题的求解中发挥着越来越重要的作用。

二、  贪心策略的定义

【定义1】 贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。

其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。

三、贪心算法的特点

    通过上文的介绍，可能有人会问：贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：

1、贪心选择性质：

所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。

2、局部最优解：

我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，在广度优先搜索（BFS）中的解题过程亦可以满足局部最优解。

在遇到具体问题时，许多选手往往分不清哪些题该用贪心策略求解，哪些题该用动态规划法求解。在此，我们对两种解题策略进行比较。

                     图  1

【引例】在一个N×M的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。

3

4

6

1

2

10

   我们以2×3的矩阵为例。

   若按贪心策略求解，所得路径为：1→3→4→6；                                图  二

若按动态规划法求解，所得路径为：1→2→10→6。                                         

a

a

a

a

a

a

a

a

a

a

a

a

由于贪心策略自身的特点，使得数字10所在的格子成为一个“坏格子”，即运用贪心策略找不到它，而运用动态规划法求解的第一步（1→2）并不是最优选择，但却保证了全局最优解；运用贪心策略求解的第一步（1→3）保证了

                                        图  三 

局部最优解，却无法保证全局最优解。我们若用图3所示的N×M的矩阵表示一组数,设运用与引例同样的移动规则后得到了由若干个元素组成的数列A。可得如下结论：      

若a >a ,则a 、a 、…a 一定不在数列A中。对于一元素a (2≤p≤m)，设a =∞，若保证全局最优解，则a 必在数列A中，但运用贪心策略求解时a 不在数列A中。由此可见，贪心策略并不到达问题状态的全部空间。若用空间图来表示贪心算法和动态规划算法（如下图），我们可以清楚地看到，贪心算法

 问题状态空间              动态规划所用空间      贪心策略所用空间

 图  4

是一种对输入数据进行不断收缩的过程。它并不到达问题的全部状态空间。这是由本文所述的贪心策略的线形解题框架所决定的。

四、  贪心策略的理论基础

——矩阵胚

正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论——矩阵胚。

“矩阵胚”理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。

【定义3】  矩阵胚是一个序对M=[S，I] ，其中S是一个有序非空集合，I是S的一个非空子集，成为S的一个独立子集。

如果M是一个N×M的矩阵的话，即

           a , a ,......, a

           . . . . . .

   M=     a , a ,......, a

           . . . . . .

           a , a ,......, a  

S是M的各个行，S=（a , a ,......, a ），I是线形无关的若干行a , a , a ......

   若M是无向图G的矩阵胚的话，则S为图的边集，I是所有构成森林的一组边的子集。

   如果对S的每一个元素X（X∈S）赋予一个正的权值W（X），则称矩阵胚M=（S，I）为一个加权矩阵胚。

适宜于用贪心策略来求解的许多问题都可以归结为在加权矩阵胚中找一个具有最大权值的独立子集的问题，即给定一个加权矩阵胚，M=（S，I），若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。

我们认为，针对绝大多数的信息学问题，只要它具备了“矩阵胚”的结构，便可用贪心策略求解。矩阵胚理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。

五、  几种典型的贪心算法

   贪心策略在图论中有着极其重要的应用。诸如Kruskal、 Prim、 Dijkstra等体现“贪心”思想的图形算法更是广泛地应用于树与图的处理。下面就分别来介绍Kruskal算法、Prim算法和Dijkstra算法。

Ⅰ、库鲁斯卡尔（Kruskal）算法

【定义4】 设图G=（V，E）是一简单连通图，｜V｜ =n,｜E｜=m,每条边ei都给以权W ，W 假定是边e 的长度（其他的也可以），i=1，2，3，...，m。求图G的总长度最短的树，这就是最短树问题。

    kruskal算法的基本思想是：首先将赋权图G的边按权的升序排列，不失一般性为：e ,e ,......,e 。其中W ≤W ，然后在不构成回路的条件下择优取进权最小的边。

    其流程如下：

    （1） 对属于E的边进行排序得e ≤e ≤...... ≤e 。

    （2） 初始化操作  w←0，T←ф ，k←0，t←0；

    （3） 若t=n-1，则转（6），否则转（4）

    （4） 若T∪｛e ｝构成一回路，则作

                 【k←k+1，转（4）】

    （5） T←T∪{ e }，w←w+ w ，t←t+1，k←k+1，转（3）

    （6） 输出T，w，停止。

     下面我们对这个算法的合理性进行证明。

设在最短树中，有边〈v ，v 〉，连接两顶点v ，v ，边〈v ，v 〉的权为wp，若〈v ，v 〉加入到树中不能保证树的总长度最短，那么一定有另一条边〈v ，v 〉或另两条边〈v ，v 〉、〈v ，v 〉，且w<vi，vj><wp或w<vi，vk>+w〈vk，vj〉<wp，因为〈v ，v 〉、〈v ，v 〉不在最短树中，可知当〈v ，v 〉、〈v ，v 〉加入到树中时已构成回路，此时程序终止。因为〈v ，v 〉∈ T，〈v ，v 〉∈T且w〈vI，vk〉+w〈vk，vj〉<w p，与程序流程矛盾。

Ⅱ、普林（Prim）算法：

   Kruskal算法采取在不构成回路的条件下，优先选择长度最短的边作为最短树的边，而Prim则是采取了另一种贪心策略。

    已知图G=（V，E），V={v ，v ，v ，...， v }，D=（d ） 是图G的矩阵，若〈v ，v 〉∈E，则令dij=∞，并假定dij=∞

    Prim算法的基本思想是：从某一顶点（设为v ）开始，令S←｛v ｝，求V\S中点与S中点v 距离最短的点，即从矩阵D的第一行元素中找到最小的元素，设为d ，则令S←S∪ { v }，继续求V\S中点与S的距离最短的点，设为v ,则令S←S∪{ v }，继续以上的步骤，直到n个顶点用n-1条边连接起来为止。

流程如下：

(1)    初始化操作：Ｔ←ф，ｑ（1）←-1，ｉ从２到ｎ作

【ｐ（ｉ）←1，ｑ（ｉ）←ｄｉ１】，ｋ←1

(2) 若ｋ≥n,则作【输出T,结束】

否则作【min←∞，ｊ从２到ｎ作

【若０<q(i)<min则作

【min←q(i) h←j】

　　　　　　　　　　】

　　　　　　　　】

(3) Ｔ←Ｔ∪{ｈ，p(h)},q(h)←-1

(4) ｊ从２到ｎ作

　　　　 【若d <q(j)则作【q(j)←d ,p(j)←h】】

(5) ｋ←ｋ＋１，转(2)

    算法中数组p（i）是用以记录和v 点最接近的属于S的点，q（i）则是记录了v 点和S中点的最短距离，q（i）=-1用以表示v 点已进入集合S。算法中第四步：v 点进入S后，对不属于S中的点vj的p（j）和q（j）进行适当调整，使之分别记录了所有属于S且和S距离最短的点和最短的距离，点v , v ，…，v 分别用1，2，…,n表示。

Ⅲ、戴克斯德拉（Dijkstra）算法：

    已知图G=（V，E），V={v ，v ，..., v }，起始顶点v ，求v 点到其他各点的最短路径。

    算法如下：

令S表示已求出最短路径的顶点集合。对于不在S中的顶点w，令d（w）表示从v 开始且通过S中的顶点到达w的最短路径的长度。S的初态为空，若v 通过S中的顶点到w有路径，则d（w）为v 到w的最短的一条路径的长度；若v 没有经S中的顶点到w的路径，则d（w）=∞，初始时设d（v ）=0，除v 外的所有顶点v v （v ∈V且v ≠v ），d（v ）=∞。

六、   贪心策略的应用

在现实世界中，我们可以将问题分为两大类。其中一类被称为P类问题，它存在有效算法，可求得最优解；另一类问题被称为NPC类问题，这类问题到目前为止人们尚未找到求得最优解的有效算法，这就需要每一位程序设计人员根据自己对题目的理解设计出求较优解的方法。下面我们着重分析贪心策略在求解P类问题中的应用。

§6.1   贪心策略在P类问题求解中的应用

§6.1.1 贪心策略在求P类最优解问题中的应用

在现实生活中，P类问题是十分有限的，而NPC类问题则是普遍的、广泛的。在国际信息学奥林匹克竞赛的发展过程中，由于受到评测手段的限制，在1989年至1996年的8年赛事中，始终是以P类问题为主的，且只允许求最优解。在这些问题中，有的题目可以用贪心策略来直接求解，有的题目运用贪心策略后可以使问题得到极大的简化，使得程序对大信息量的处理提供了可能。

[例1]删数问题

试题描述  键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N和S，寻找一种删数规则使得剩下得数字组成的新数最小。

试题背景  此题出自NOI94

试题分析  这是一道运用贪心策略求解的典型问题。此题所需处理的数据从表面上看是一个整数。其实，大家通过对此题得深入分析便知：本题所给出的高精度正整数在具体做题时将它看作由若干个数字所组成的一串数，这是求解本题的一个重要突破。这样便建立起了贪心策略的数学描述。.

[例2]数列极差问题

试题描述   在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。

编程任务：对于给定的数列，编程计算出极差M。

试题背景  这是1997年福建队选拔赛的一道题目。

试题分析  当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。

　　下面我们以求max为例来讨论此题用贪心策略求解的合理性。

讨论：假设经（Ｎ－3）次变换后得到３个数：a,b,max＇

（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为Ｚ ，Ｚ ，则有：Ｚ ＝（ａ×ｂ＋１）×max＇＋１，Ｚ ＝（ａ×max＇＋１）×ｂ+１　所以　Ｚ －Ｚ ＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，ｂ（ｍ≥ａ≥ｂ）且ｍ不为（Ｎ－２）次变换后的最大值，即ｍ＜max＇则此时所求得的最大值为：Ｚ ＝（ａ×ｂ+１）×ｍ+１　此时Ｚ －Ｚ ＝（１+ａｂ）（max＇－ｍ）＞０　所以此时不为最优解。

　　所以若使第ｋ（１≤ｋ≤Ｎ－１）次变换后所得值最大，必使（ｋ－１）次变换后所得值最大（符合贪心策略的特点2），在进行第ｋ次变换时，只需取在进行（ｋ－１）次变换后所得数列中的两最小数ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←∞即可（符合贪心策略特点1），因此此题可用贪心策略求解。讨论完毕。

　　在求ｍｉｎ时，我们只需在每次变换的数列中找到两个最大数ｐ，ｑ施加作用ｆ：ｐ←ｐ×ｑ+１，ｑ←-∞即可．原理同上。

　　这是一道两次运用贪心策略解决的一道问题，它要求选手有较高的数学推理能力。

［例３］最优乘车问题

试题描述　Ｈ城是一个旅游胜地，每年都有成千上万的人前来观光．为方便游客，巴士公司在各个旅游景点及宾馆、饭店等地都设置了巴士站，并开通了一些单向巴士线路。每条单向巴士线路从某个巴士站出发，依次途径若干个巴士站，最终到达终点巴士站。

　　阿昌最近到Ｈ城旅游，住在ＣＵＰ饭店。他很想去Ｓ公园游玩。听人说，从ＣＵＰ饭店到Ｓ公园可能有也可能没有直通巴士。如果没有，就要换乘不同线路的单向巴士，还有可能无法乘巴士到达。

　　现在用整数１，２，...，ｎ给Ｈ城的所有巴士站编号，约定ＣＵＰ饭店的巴士站编号为１，Ｓ公园巴士站的编号为Ｎ。

写一个程序，帮助阿昌寻找一个最优乘车方案，使他在从ＣＵＰ饭店到Ｓ公园的过程中换车的次数最少。

试题背景  出自ＮＯＩ９７

试题分析  此题看上去很像一道搜索问题。在搜索问题中，我们所求的使经过车站数最少的方案，而本题所求解的使换车次数最少的方案。这两种情况的解是否完全相同呢？我们来看一个实例：

                         图   5

　　如图5所示：共有５个车站（分别为ａ、ｂ、ｃ、ｄ、ｅ），　共有３条巴士线（线路Ａ：ａ→ｄ；线路Ｂ：ａ→ｂ→ｃ→ｅ；线路Ｃ：ｄ→ｅ）。此时要使换车次数最少，应乘坐线路Ｂ的巴士，路线为：ａ→ｂ→ｃ→ｅ，换车次数为０；要使途经车站数最少，乘坐线路应为ａ→ｄ→ｅ，换车次数为１。所以说使换车次数最少的路线和使途经车站数最少的方案不一定相同。这使不能用搜索发求解此问题的原因之一。

原因之二，来自对数学模型的分析。我们根据题中所给数据来建立一个图后会发现该图中存在大量的环，因而不适合用搜索法求解。

题目分析到这里，我们可以发现此题与NOI93的求最长路径问题有相似之处。其实，此题完全可以套用上文所提到的Dijkstra算法来求解。

以上三道题只是使用了单一的贪心策略来求解的。而从近几年的信息学奥林匹克竞赛的命题方向上看，题目更加灵活，同时测试数据较大，规定的出解时间较短。在一些问题中，我们采用贪心策略对问题化简，从而使程序具有更高的效率。

［例４］最佳浏览路线问题

试题描述　某旅游区的街道成网格状（见图），其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。

　　阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路值得浏览得程度，分值从-１００到１００的整数，所有林荫道不打分。所有分值不可能全是负值。

　　例如下图是被打过分的某旅游区的街道图：

　　                  图6

阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。

试题背景　　这道题同样出自ＮＯＩ９７，＇９７国际大学生程序设计竞赛的第二题（吉尔的又一个骑车问题）与本题是属于本质相同的题目。

试题分析  由于林荫道不打分，也就是说，无论游客在林荫道中怎么走，都不会影响得分。因题可知，若游客需经过某一列的旅游街，则他一定要经过这一列的Ｍ条旅游街中分值最大的一条，才会使他所经路线的总分值最大。这是一种贪心策略。贪心策略的目的是降维，使题目所给出的一个矩阵便为一个数列。下一步便是如何对这个数列进行处理。在这一步，很多人用动态规划法求解，这种算法的时间复杂度为Ｏ（ｎ ），当林荫道较多时，效率明显下降。其实在这一步我们同样可以采用贪心法求解。这时的时间复杂度为Ｏ（ｎ）。

§6.1.2  贪心策略在求P类较优解问题中的应用

    正如其他学科奥林匹克竞赛一样，国际信息学奥赛的发展同样经历了一个逐步成熟的发展过程。回顾十余年赛事的发展，我们不妨将国际信息学奥赛的发展分为两个阶段：第一阶段是1989—1996年，这一时期奥赛题目的特点是：试题全部为P类问题，且只允许求最优解，题目的设计强调对选手基本算法的掌握。第二阶段为1997年至今。在南非举行的IOI97中，命题方向一举突破传统模式，NPC类问题在竞赛中大量出现，每道题目到具有一定的实际背景，引进了崭新的程序评测机制。在求解P类问题时允许得出较优解并得到相应的分数。这些变化无疑更好地考察了选手的综合素质。在对P类较优解问题的求解过程中，贪心策略无疑扮演着重要角色。IOI97中的障碍物探测器问题便是运用贪心策略来求得较优解的P类问题。

[例5] 障碍物探测器问题

试题描述 有一个登陆舱（POD），里面装有许多障碍物探测车（MEV），将在火星表面着陆，着陆后，探测车离开登陆舱向相距不远的先期到达的传送器（Transmitter）移动。MEV一边移动，采集岩石（ROCK）标本，岩石由第一个访问到它的MEV所采集，每块岩石只能被采集一次，但是这以后，其他MEV可以从该处通过。探测车MEV不能通过有障碍的地面。

本题限定探测车MEV只能沿着格子向南或向东从登陆处向传送器transmitter移动，允许多个探测车MEV在同一时间占据同一位置。

警告：如果某个探测车MEV在到达传送器以前不能在继续合法前进时，则车中的石块必定不可挽回地全部丢失。

任务：计算机探测车的每一步移动，使其送到传送器的岩石标本的数量尽可能多。这两项都做到会使你的得分最高。

输入：火星表面上登陆舱POD和传送器之间的位置用网格P和Q表示，登陆舱POD的位置总是在（1，1）点，传送器的位置总是在（P，Q）点。

火星上的不同表面用三中不同的数字符号来表示：

●  0代表平坦无障碍

●  1代表障碍

●  2代表石块

输入文件的第一行为探测车的个数，第二行为P的值，第三行为Q的值。接下来的Q行为一个Q×P的矩阵。

输出：表示MEV移向transmitter的行动序列。每行包含探测车号和一个数，0或1，这里0表示向南移动，1表示向东移动。

得分：分数的计算将根据收集的岩石样本（取到传送器上）的数目，MEV到达传送器和不到达传送器的数目有关

●  非法移动将导致求解无效，并记作零分，当MEV的障碍物上移动或移出网格，即视为非法。

●  得分=（收集的样品并取到传送器上的数目+MEV到达传送器上的数目-MEV没有到达传送器上的数目）与应得的最大的数目之比（%）

●  最高分为100%，最低分为0%

试题背景 IOI’97中的第一试第一题。国际信息学奥赛中出现的第一道NPC类问题。1997年美国的探测器再次到达火星。火星及太空搜索引起了人们的广泛关注，此题便是以此为素材而创作的。

试题分析 关于迷宫问题相信每一个参加信息学奥赛的选手都不会陌生。对于不同的迷宫，我们可用搜索策略或动态规划进行求解。在本题中，无论运用哪种解题策略均不能得到问题的最优解，我们的任务是合理选择一种解题策略，使我们运用该策略得到的较优解尽可能地接近最优解。我们先来看一个例子（如图7所示）。对于一个探测车而言，我们运用动态规划的方法使探测车经过岩石最多的一条路线便可得到问题的最优解（如图8所示），这时共可收集到岩石10个。

            图  7                      图  8

当有2个探测车时，我们让第2辆探测车在图8的基础上从地图的起点S行进至终点f（如图9所示），这时我们共收集到岩石15个。而实际上两辆探测车可收集到地图中的全部岩石（共16个），

      图   9                     图  10

当探测车数量为3时，我们可以收集到全部的16个岩石。

我们可让从起点出发的每一辆探测车都收集到尽可能多的岩石，这实际上是一种贪心策略。对于本题而言，贪心策略并不能保证所得结果全部为最优解，但由于每一辆探测车都收集尽可能多的岩石，而对于由计算机随机产生的测试数据而言，岩石是比较均匀地分布在地图中的，于是我们认为：

探测车收集岩石数≈探测车所游历的地图空间

让每一辆探测车收集尽可能多的岩石，也就是让探测车经过尽可能大的地图空间。所以在探测车数量逐渐增多时，所有探测车所经过的地图空间越多，收集到的岩石也就越多，此时也就越接近最优解。

此题是否存在最优解呢？其实，我们可以用网络流的算法来解决此题。但实践证明，用网络流算法去求解本题所占空间较大，编程复杂度较高且程序调试起来较为困难，因此在实际比赛中，在限定的时间内用贪心策略完成对题目的求借不失为上策。

§6.2 关于运用贪心策略求解NPC类问题的讨论

  正如前面所讲的那样，在南非举行的第九届国际奥林匹克信息学竞赛中首次引入了NPC类问题，在杭州举行的NOI98中引入了NOI发展史上的第一道NPC类问题——并行计算。可以说，NPC类问题正在日益引起人们的兴趣。它要求选手根据题意自己建立适当的模型，使程序的解尽量逼近最优解。目前，信息学竞赛所涉及到的少量NPC类问题主要是运用贪心策略或随机化算法去求较优解的。但是对于同一道NPC类问题来说，运用不同的贪心选择所求得的最优解是不同的，不同的贪心选择针对不同的测试数据所得解与最优解的逼近程度也是不同的。所以有关NPC类问题的众多特性以及哪些问题运用贪心策略求得的较优解逼近于最优解仍是需要我们花费大量精力去研究的。信息学奥林匹克的精华—激励创新也许在求解NPC类问题时会得到最大程度的体现。

七、  总结

　　通过对贪心策略的分析，大家可以看出：贪心策略作为一种高效算法，广泛地应用与信息学奥林匹克竞赛中。即使表面上看起来与贪心策略关系甚微的题目，运用贪心算法也可使程序的运行效率大大提高。因此，深刻理解贪心策略的数学模型、特点、理论基础、尤其是运用其基本思想解决具体问题是十分重要的。希望本文能给参赛选手以一定的启发。

【附 录】

【参考书目】

１　《实用算法的分析与程序设计》

吴文虎，王健德编著，电子工业出版社，ISBN 7-5053-4402-1

２　《计算机算法导引》

 卢开澄编著，清华大学出版社，ISBN 7-302-02277-1

3、 《国际大学生程序设计竞赛试题解析》

      王建德，柴晓路编著，复旦大学出饭社

ISBN 7-309-02141-X/T·210