资源简介

贪心算法
在实际生活中，经常需要求一个问题的可行解和最优解，这就是所谓的最优化问题。每
个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解方案称为可行
解，使优化函数取得最佳值的可行解称为最优解。
贪心法是求解这类问题的一种常用算法，它是从问题的某一个初始解出发，采用逐步构
造最优解的方法向给定的目标前进。在每个局部阶段，都做出一个看上去最优的决策（即某
种意义下的、或某个标准下的局部最优解），并期望通过每次所做的局部最优选择产生出一
个全局最优解。但采用贪心法求解不能保证对所有问题都能得到最优解，这时我们可以选择
其它解决最优化问题的算法，如动态规划等。
做出贪心决策的依据称为贪心准则（策略），注意决策一旦做出，就不可再更改。贪心
与递推不同的是，推进的每一步不是依据某一固定的递推式，而是做一个当时看似最佳的贪
心选择（操作），不断地将问题实例归纳为更小的相似子问题。所以，归纳、分析、选择正
确合适的贪心准则，是正确解决贪心问题的关键。下面我们先看两个简单而典型的例子。
例 1、删数问题
[问题描述] 键盘输入一个高精度的正整数 n(≤240 位)，去掉其中任意 s个数字后剩下
的数字按原左右次序将组成一个新的正整数。编程对给定的 n 和 s，寻找一种方案，使得剩
下的数字组成的新数最小。
[输入格式] n
s
[输出格式] 最后剩下的最小数。
[样例输入] 178543
4
[样例输出] 13
[算法分析]
由于正整数 n 的有效数位为 240 位，所以很自然地采用字符串类型存贮 n。那么如何决
定哪 s位被删除呢？是不是最大的 s个数字呢？显然不是，大家很容易举出一些反例。为了
尽可能逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，
即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减
区间的首字符，这样删一位便形成了一个新数字串。然后回到串首，按上述规则再删下一个
数字。重复以上过程 s次为止，剩下的数字串便是问题的解了。
例如：n=178543
s=4
删数的过程如下：
n=178543 {删掉 8}
17543 {删掉 7}
1543 {删掉 5}
127
143 {删掉 4}
13 {解为 13}
这样，删数问题就与如何寻找递减区间首字符这样一个简单的问题对应起来。不过还要
注意一个细节性的问题，就是可能会出现字符串串首有若干 0的情况，甚至整个字符串都是
0的情况。按以上贪心策略编制的程序框架如下：
输入 n，s；
while s>0 do
begin
i：=1； {从串首开始找}
while (idelete (n，i，1)； {删除字符串 n的第 i个字符}
s:=s-1；
end；
while (length(n)>1)and (n[1]=‘0’) do delete(n，1，1)；
{删去串首可能产生的无用零}
输出 n；
例 2、取数游戏
[问题描述] 给出 2*n(n<=100)个自然数（数小于等于 30000）。游戏双方分别为 A方（计
算机方）和 B方（对奕的人）。只允许从数列两头取数。A先取，然后双方依次轮流取数。取
完时，谁取得的数字总和最大为取胜方；双方和相等，属于 A胜。试问 A方可否有必胜的策
略？
[输入格式] 键盘输入 n及 2*n 个自然数。
[输出格式] 共 3*n+2 行，其中前 3*n 行为游戏经过。每 3 行分别为 A 方所取的数和 B
方所取的数，及 B方取数前应给予的适当提示，让游戏者选择取哪一头的数（L/R—左端或右
端）。最后 2行分别为 A方取得的数和和 B方取得的数和。
[算法分析]
设 n=4，自然数列为:7 9 3 6 4 2 5 3，我们设计一种原始的贪心策略，让 A每
次取数列两头较大的那个数，则游戏者也不会傻，他也会这么干，所以在上面的数列中，A
方会顺序取 7、3、4、5，B方会顺序取 9、6、2、3，由此得出：A方取得的数和为 7+3+4+5=19，
B方取得的数和为 9+6+2+3=20，按照规则，判定 A方输。
其实，如果按上述贪心策略去游戏，成败取决于给你的测试数据！不过，虽然 A方败给
B方，但是我们却发现了一个有趣的事实：A方取走偶位置的数后，剩下两端数都处于奇位置；
反之，若 A 方取走奇位置的数后，剩下两端数都处于偶位置。即无论 B 方如何取法，A 方即
可以取走奇位置的所有数，亦可以取走偶位置的所有数。由此萌发出另一种有效的贪心策略：
若能够让 A方取走“数和较大的奇（或偶）位置上的所有数”，则 A方必胜。这样，取数问题
便对应于一个简单问题：让 A方取奇偶位置中数和较大的一半数。设 j为 A取数的奇偶位置
标志，则 j=0 表示偶位置数和较大，A取偶位置上的所有数；j=1 表示奇位置数和较大，A取
奇位置的所有数。
128
设 SA，SB 分别表示 A方取数和，B方取数和（SA≥SB）；a存储 2*n 个自然数序列；lp，
rp 为序列的左端位置和右端位置；ch为 B方取数的位置信息（’L’或’R’）；按上述贪心思
想编写的程序框架如下：
读入 n及 a；
SA：=0；SB：=0； {计算 A方取数和、B方取数和，A方取数的位置标志}
for i：=1 to n do
begin
SA：=SA+a[2*i-1]；SB：=SB+a[2*i]；
end；
if SA>=SB then j:=1
else begin j:=0；交换 SA 和 SB；end；
lp：=1；rp：=2*n；
for i：=1 to n do {A 方和 B方依次进行 n次对奕}
begin
if ((j=1) and (lp mod 2=1)) or ((j=0)and (lp mod 2=0)) {若 A方应取奇位
置数且左端位置为奇，或者 A方应取偶位置数且左端位置为偶，则 A方取走左端位置的数}
then begin writeln(a[lp])；lp：=lp+1；end {输出}
else begin writeln(a[rp])；rp：=rp-1；end；
write(‘ B=L/R ’)；{提示信息}
repeat {B 方取数，输入 L或 R}
readln(ch)；
if ch=‘L’ then begin write(a[lp])；lp：=lp+1；end； {输出}
if ch=‘R’ then begin writeln(a[rp])；rp：=rp-1；end；
until （ch=‘L’） or (ch=‘R’)；
end；
输出 A 方取数的和 SA 和 B 方取数的和 SB；
小结：
以上两个例题所用的贪心思想还是很明显的，选取的贪心策略也很直观（可能也是唯
一的）；不仅能得到最优解，而且解的正确性也可以得到严格的证明。但有些问题采用贪心法
求解时，贪心策略可能有多种，在针对性不同的测试数据下，带来的效果可能也不一样，并
不是总能得到最优解，而且解的正确性证明也很困难。最典型的例子就是 0/1 背包问题。
例3、0/1背包问题
[问题描述] 有一容量为weight的背包。现在要从n件物品中选取若干装入背包中，每件
物品i的重量为w[i]，价值为p[i]。定义一种可行的背包装载为：背包中物品的总重量不能超
过背包的容量，并且一个物品要么全部选取，要么不选取。定义最佳装载是指所装入的物品
价值最高，并且是可行的背包装载。
[样例输入]
11 {weight}
129
4 {n}
2 4 6 7 {w[i]}
6 10 12 13 {p[i]}
[样例输出]
0 1 0 1
23
[问题分析]
设数组choice[1..n]，若choice[i]=1表示物品i装入背包中，choice[i]=0表示物品i不
装入背包中。则choice=[0，1，0，1]是一种可行的背包装载方案，也是一种最佳装载方案，
此时总价值为23。
0/1 背包问题有好几种贪心准则，每种贪心准则都是采用多步过程来完成背包的装入，
在每一步过程中利用某种固定的贪心准则选择一个物品装入背包。
一种贪心准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规
则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此
继续下去。这种贪心准则不能保证得到最优解。例如 weight=105，n=3，w=[100，10，10]，
p=[20，15，15]。按照以上这种“价值贪心准则”，获得的解为 choice=[1，0，0]，这种方
案的总价值为 20。而最优解为 choice =[0，1，1]，其总价值为 30。
另一种方案是“重量贪心准则”，即从剩下的物品中选择可装入背包的重量最小的物品。
虽然这种规则对于前面的例子能产生最优解，但在一般情况下不一定能得到最优解，例如
weight=25，n=2，w=[10，20]，p=[5，100]。获得的解为choice=[1，0]，总价值为5，比最
优解choice =[0，1]的总价值100要差。
本题的另一方案为“单位价值贪心准则”，这种方案是从剩余物品中选择可装入包的p[i]
/w[i]值最大的物品，这种策略也不能保证得到最优解。例如weight=30，n=3，w=[20，15，
15]，p=[40，25，25]。获得的解为choice=[1，0，0]，总价值为40。而最优解为choice=[0，
1，1]的总价值为50。
既然任何一种贪心策略都不能保证得到最优解，那么本题是不是不应该用贪心法？其实
我们不必因所考察的几个贪心策略都不能保证得到最优解而沮丧（或放弃），因为 0/1 背包
问题是一个复杂的 NP问题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。
虽然按“单位价值贪心准则”递减的次序装入物品不能保证得到最优解，但它是一个直觉上
近似的解，而且时间复杂度仅为 O(nlogn)。造成多种贪心都不能全对的原因其实在于，在很
多情况下，无法将背包填满，空间上的浪费间接降低了实际上的单位价值。当然本题很有一
种思路，就是用动态规划求解。
小结：
与这个题目类似的问题很多，比如部分背包问题、船的最优装载问题、硬币的最少组合
问题、多机调度问题等。留给大家回去思考：哪些可以用贪心法、哪些不可以。
例 4、活动选择
130
[问题描述] 假设有一个需要使用某一资源的 n个活动组成的集合 S，S={1，……，n}。
该资源一次只能被一个活动所占用，每一个活动有一个开始时间 bi和结束时间 ei (bi≤ei)。
若 bi≥ej或者 bj≥ei，则活动 i和活动 j兼容。
你的任务是:选择由互相兼容的活动组成的最大集合。
[输入格式] 输入文件名为：act.in，共 n+1 行，其中第 1行为 n，第 2行到第 n+1 行表
示 n个活动的开始时间和结束时间（中间用空格隔开），格式为：
n
b1 e1
………
bn en
[输出格式] 输出文件名为：act.out，共两行，第 1行为满足要求的活动占用的时间 t，
第 2行为最大集合中的活动序号，每个数据之间用一个空格隔开。
[样例输入]
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
[样例输出]
14
2 3 6 8
[算法分析]
我们使用的贪心策略如下，即每一步总是选择这样一个活动来占用资源：它能够使得余
下的未调度时间最大化，使得兼容的活动尽可能多。为了达到这个目的，我们将 n个待选活
动按结束时间递增的顺序排列：e1’≤e2’≤……≤en’。
首先将递增序列中的活动1进入集合S。然后依次分析递增序列中的活动2，活动3，……，
活动 n，每次将与 S中的活动兼容的活动加入到集合 S中。
我们结合问题的样例输入，先将 11 个活动的活动号、开始时间、结束时间及递增编号
列表（表 1）如下：
表 1
活动序号 i 开始时间 b[i] 结束时间 e[i] 按活动结束时间递增的序号 j
131
1 3 5 2
2 1 4 1
3 12 14 11
4 8 12 9
5 0 6 3
6 8 11 8
7 6 10 7
8 5 7 4
9 3 8 5
10 5 9 6
11 2 13 10
按照以上这种贪心策略，贪心选择的过程如下：
时间 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
选择活动 |—|—|—|—|—|—|—|—|—|—|—|—|—|—|
2 —————活动 2兼容（持续时间 1-4），加入 S，S={2}，t=4
1 不兼容，放弃
5 不兼容，放弃
8 ————活动 8兼容（持续时间 5-7），加入 S，S={2，8}，t=7
9 不兼容，放弃
10 不兼容，放弃
7 不兼容，放弃
6 —————活动 6兼容（持续时间 8-11），加入 S,
S={2，8，6}，t=11
4 不兼容，放弃
11 不兼容，放弃
3 ———活动 3兼容（持续时间 12-14），
加入 S，S={2，8，6，3}，t=14
所以，问题的解为：t=14，S={2，8，6，3}。根据以上算法编写的程序框架如下：
S：={1}；j：=1； {递增序列中的活动 1进入集合 S，设定最近进入 S的活动序号为 1}
for i：=2 to n do
if bi’>=ej’ {若递增序列中的活动 i与 S集合中的活动兼容}
then begin
S：=S+{i}； {活动 i进入集合 S}
t：=ei’； {计算占用时间}
j：=i； {设定最近进入 S的活动序号为 i}
end；
输出占用时间 t；
for i：=1 to n do
132
if i in S then 输出活动 i的序号；
小结：
一、 贪心算法的基本要素及与动态规划算法的关系
对于一个具体的问题，怎么知道是否可以用贪心算法求解呢？得到的解是不是问题的最
优解呢？这个问题很难给予肯定的回答。但是一般来说这类问题具有两个重要的性质：
1、 贪心选择性质：即问题的整体最优解可以通过一系列局部最优的贪心选择达到。
这是贪心法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
在动态规划算法中，每步所做出的选择往往依赖于相关子问题的解。因而只有
解出相关子问题后，才能做出选择。而贪心算法是先做出当前的局部最优选择，
然后再去解这个选择后产生的相应子问题。所以，贪心算法可以依赖以往所做
的选择，但决不依赖将来所做的选择，也不依赖子问题的解。
对于一个具体问题，我们一般通过数学归纳法证明他是否具有贪心选择性
质。但在实际比赛中，由于时间等因素，一般不会严格地证明，而是要把问题
的各个方面、各种情况考虑清楚，多找数据测试和验证。
2、 最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具
有最优子结构性质。这一性质是决定一个问题可否采用贪心或动态规划算法的
关键特性。比如，在例 4 的活动安排中，其最优子结构性质表现为：若 S 是关
于 E 的活动安排问题的包含活动 1 的一个最优解，则相容活动集合 S’=S-{1}
是关于 E’={i 属于 E : bi>=e1}的活动安排问题的一个最优解。
虽然贪心算法和动态规划算法都要求问题具有最优子结构性质，但两者不是通用的。比
如前面讲到的 0/1 背包问题和部分背包问题，都具有最优子结构性质，但前者不可以用贪心，
而只能用动态规划，本质原因是：存在空间上的浪费；而后者是是可以用贪心求的最优解。
另外，一般而言贪心算法的效率比动态规划要高。
二、 思考树和图论中的哪些算法是采用的贪心思想。
哈夫曼编码问题、Dijkstra 算法求解单源最短路径问题、Prim 算法和 Kruskal 算法求
解最小生成树问题。
例 5、雇佣计划
[问题描述] 一位管理项目的经理想要确定每个月需要的工人，他当然知道每月所需的
最少工人数。当他雇佣或解雇一个工人时，会有一些额外支出。一旦一个工人被雇佣，即使
他不工作，他也将得到工资。这位经理知道雇佣一个工人的费用，解雇一个工人的费用和一
个工人的工资。现他在考虑一个问题：为了把项目的费用控制在最低，他将每月雇佣或解雇
多少个工人。
[输入格式] 输入文件含有三行。第一行为月数 n（不超过 12）。第二行含雇佣一个工人
的费用，一个工人的工资和解雇一个工人的费用（≤100）。第三行含 n个数，分别表示每月
最少需要的工人数（≤1000）。每个数据之间有一个空格隔开。
[输出格式] 输出仅一行，表示项目的最小总费用。
[输入样例]
133
3
4 5 6
10 9 11
[输出样例]
199
[算法分析]
我们从第一个月开始，逐月计算现有工人数，先给这些工人发放工资。如果雇佣了新工
人，则必须给新上岗人员发放雇佣费用；如果削减了部分工人，则必须给下岗人员发放解雇
费用。当月发放的工资+雇佣（或解雇）费用构成了一个月的总费用。我们从第一个月开始，
逐月累计项目总费用，直至计算出 n个月的总费用为止。问题是怎样将这笔费用控制在最低？
设 mincost 表示最小费用和，初始时 mincost=0；now 表示现有工人数，初始时 now=0；min[i]
表示第 i个月所需要的最少工人数（1≤i≤n）；n表示月数；f表示解雇费用；s表示工资；
h表示雇佣费用。则我们需要解决下面的两个问题：
1、怎样在当月工人数不足的情况下确定雇佣方案
如果第 i个月的所需最少人数 min[i]大于现有工人数 now，则需要雇佣工人。为了尽可
能少地减少雇佣费用，我们不妨雇佣(min[i]-now)个工人，使得第 i 个月的工人数正好为
min[i]；如果 min[i]=now，则维持现有工人数 now 不变。算法思想如下：
if min[i]>now
then begin
mincost：=mincost+h*(min[i]-now)；now：=min[i]；
end；
mincost：=mincost+now*s； { 显然，这样的雇佣费用支出是最节约的 }
2、怎样在当月工人数多余的情况下确定解雇方案
如果现有工人数 now 大于第 i个月最少需要的工人数 min[i]，则需要解雇一部分工人，
最佳方案是否一定是解雇(now-min[i])个工人呢？不是的。例如对于示例中的数据，依上述
方法计算：
第 1个月雇佣 10人：mincost=mincost+h*(min[i]-now)+s*min[i]
=0+4*10+5*10
=90 now=10
第 2个月解雇 1人，使得现有工人数为 9人：
mincost=mincost+f*(now-min[2])+d*min[2]
=90+6*1+9*5
=141 now=9
第 3个月雇佣 2人，使得现有工人数为 11人：
mincost=mincost+h*(min[3]-now)+d*min[3]
=141+4*2+5*11
=204 now=11
134
显然，该雇佣计划的总费用（204）并不是最少的，因为如果第 2 个月不解雇 1 人，仍
维持 10人，第 3个月再雇佣 1人，这种情况下的总费用为（4*10+5*10）+（5*10）+（4*1+5*11）
=90+50+59=199，即为样例输出。由此看出，解雇的人数应比(now-min[i])少一些，那么少多
少呢？我们采取这样的贪心策略去确定：尽可能少地解雇工人，并且在工资支出合理的前提
下尽可能使现有工人数维持在一个最长时间内，以减少雇佣和解雇的额外支出。
实现的方法是：在 min[i]～min[n]间按最少需要人数递增的顺序，将月份排成序列 y1 ，
y2，……，yn-i，yn-i+1(其中 i≤yj≤n，1≤j≤n-i+1，如图 1)。从第 yj个月出发按照最少需要
递减的顺序检查 min[yj]、min[yj-1]，……，一旦发现第 yj月超员，且这些工人在第 yj+1个月
雇佣与第 i 到第 yj 月期间解雇的总费用，比第 i 到第 yj 个月连续使用的费用节约，即
（min[yj]n)))，则
在第 i个月解雇 now-min[yj]个工人，使现有工人数变为 min[yj]；否则维持现有工人数不变。
图 1
算法思想如下：
在 min[i]～min[n]间按最少需要人数递增的顺序，将月份排成 y1，……，yn-i+1；
for j:=n-i downto 1 do
if (min[yj]then begin
mincost：=mincost+f*(now-min[yj])；now：=min[yj]；
and
mincost：=mincost+s*now；
我们从 i=1 开始，依上述办法逐月累计费用总和，直至 i=n 为止。此时的费用总和最少。
例如对于示例中的数据，依上述方法计算：
第 1个月雇佣 10人，费用总和为 90；
第 2个月维持现有人数不变，费用总和为 90+5*10=140；
第 3个月雇佣 1人，工人数增至 11，费用总和为 140+5*11-14=199。
显然，这个答案与样本输出一致。结合上述分析得出本题总的算法框架如下：
mincost：=0；now：=0； {初始化}
for i：=1 to n do
begin
if min[i]>now
135
then 在现有人数不足情况下确定第i个月的雇佣方案并累计最小费用mincost；
else 在现有人数多余情况下确定第i个月的解雇方案并累计最小费用mincost；
end；
输出项目的最小费用 mincost；
例 6、自动柜员机 ATM
[问题描述]
在一个银行的大厅里有 100 个自动柜员机，编号分别为 0..99，每个会员顾客都能通过
30
这些柜员机提取<=10 ducats（一种早期的流通硬币单位）的借款业务，但必须在一个星期
内还是通过这些柜员机完成还款业务。这种柜员机很特别，每个柜员机只能完成一种简单的
i
动作：供客户提取固定数目的现金或接受客户固定数目的还款。第 i 个柜员机只能提供 2
i
ducats 的借款业务，如果 i是偶数的话；而如果 i是奇数的话，则第 i个柜员机只能提供 2
ducats 的还款业务。
现在，如果有一个客户想要用这些柜员机借一定数目的钱，但是每个柜员机都只能使用
一次，那么，他该使用哪些柜员机呢？
一个星期内还款时，他又该使用哪些柜员机呢？
比如，他要借7 ducats，则他会从4号柜员机拿到16 ducats，从0号柜员机拿到1 ducats，
再到 3号柜员机还掉 8 ducats，到 1号柜员机还掉 2 ducats。
一个星期内还款时，他会到 3号柜员机先还掉 8 ducats，再到 0号柜员机拿到 1 ducats。
请你编写一个程序，当一个客户借款，告诉他该使用哪些柜员机，以后还款时又该使用
哪些柜员机。
[输入]
输入文件 ban.in，第一行为整数 N（N<=1000），表示客户的数目。下面有 N行，每行为
30
一个整数，表示每个客户要借多少钱。注意：每个客户最多能借 10 ducats。
[输出]
输出文件 ban.out，共 2N行，第 2i-1 行表示客户 i借款时该使用哪些柜员机，第 2i行
表示客户 i还款时该使用哪些柜员机（1<=i<=N），每行都要求按柜员机编号从大到小输出，
每个编号之间用 1个空格隔开。
如果业务无法成交，则输出 NIE。
[样例]
ban.in
2
7
633825300114114700748351602698
ban.out
4 3 1 0
3 0
NIE
99 3 1
136
[问题分析] 贪心，时间和空间复杂度都是 O(n)。题目中说如果 odd(i)则付出，否则得
到硬币，这很容易让我们想到-2进制。
例 7、独木舟 （KAJ）
[问题描述]
我们计划组织一个独木舟旅行。租用的独木舟都是一样的，最多乘两人，而且载重有一
个限度。现在要节约费用，所以要尽可能地租用最少的舟。
[任务] 读入载重量，参加旅行的人数以及每个人的体重。计算所需要租船数目。
[输入] 文件 KAJ.IN 的第一行是 w, 80<=w<=200,每条船最大的载重量。
第二行是整数 n, 1 <= n <= 30000,参加旅行的人数。
接下来的 n行，每行是一个整数，范围[5..w]。表示每个人的重量。
[输出] 最小租用数目。
[样例输入与输出]
KAN.IN:
100
9
90
20
20
30
50
60
70
80
90
KAJ.OUT:
6
[问题分析] 贪心，找到一个重量最大的，让它尽可能与重量大的人同乘一船。如此循环
直至所有人都分配完毕。时间：O（N），空间 O（W）。
137回溯法
在程序设
优解,例
题、骑土巡游问题、迷宫问题、数的拆分、全排列问题、幂集和子集问题
虽然是按照
定的规则完成一些任务
这些任务和规则是无法用精确的数学公式来描述的
不能根据
某种确定的计算法则去生成解,而是需要采用试探和回溯的搜索策略去求解。因此,回溯法是程序
设计中解决这类问题(尤其是递归问题)的一种重要方法
法也称试探法
某一种状态
从这种状态出发所能达到的所有“状态
条路走到
时候(不能再前进),再倒
(或若干步),从另一种可能状态出发,继续搜索,直
的“路径(状态)”都试探过。这种
断“前进”、不断“回溯”寻找解的方法,称作“回溯法”。它的求解过程实质上是一个先根遍历
棵“状态空间树”的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历
探过程
态和问题所求解产生矛盾时,不再继续试探
解的终结状态。否
试探下去便能得到问题的角
解、一组
解或最优角
这类问题的
程也可以看成是在给定的(或问题蕴涵
根遍历,并在
遍历过程中剪去那些不满足条件的分支的一种搜索算法(深度或宽度)。所以,对约束条件的分析
题求解的一个关键之处
解
表示要找一条从A到B的路,我们可以用回溯的思想描述一下求解过程(不妨借助
图1找一条从A到B的路
溯法的一般模式
为了应用回溯法
的解必须能表
组(
如图1中的解便
求所有的解满
明问题,先举
家熟悉的例子
皇后问题
要求在8×8格的国际象棋上摆放8个皇后,使其不能互相攻
任意两个皇后都不处
同
同一斜线上,输出一种摆
题分析
为了解决这个问题,我们把棋盘的横坐标设定为i(
),纵坐标设定
某
)时,在这个位置的垂直方向、水
和两条斜线方向都不能再放
后了。图1便是
题
解(Q表
据的位置)
图2八皇后问题的一个解
然,在每
对每
)都有唯一的
每行
题可以表示成一个8元组
xs),其中x是放置第
行)皇后的列坐标
这个问题的约束条件是:所有的x:都不相同,即所有皇后都
保
在同一条斜线
如图2的状态便满
束条件
后问题的一个解,可以表示为以
个
貍鯉開
窜蜜
翻图翻劊鬨眩風睏
图3四皇后问题的棋盘状态树
图3是我们将八皇后问题简化为四皇后问题,它展示了求解过程中棋盘状态的变化
这是一棵四叉树,树上
点表示一个局部布局或
整的布局,根结点表示棋盘的初始
状态。每
择的
任何时刻,棋盘的合法
必须满
两个棋子都不能占据棋盘上的同一行、或者
或者同一对角线。我们发
图
展开的分支结点中除结
结点都不是合法的布局。因此,求四皇后问题的所有合法布
过程,即为在上述约束条件下先根遍
状态空间树的过
述出求
后问题的回溯算法女
八皇后问题的递归回溯算法贪心算法
在众多的计算机解题策略中，贪心策略可以算得上是最接近人们日常思维的一种解题策略，正基于此，贪心策略在各级各类信息学竞赛、尤其在对NPC类问题的求解中发挥着越来越重要的作用。
7.1 贪心策略的定义
贪心策略是：指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。
其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
例1：在n行m列的正整数矩阵中，要求从每一行中选一个数，使得选出的n个数的和最大。
本题可用贪心策略：选n次，每一次选相应行中的最大值即可。
例2：在一个N×M的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。
本题用贪心策略不能得到最优解，我们以2×4的矩阵为例。
3 4 6
1 2 10
若按贪心策略求解，所得路径为：1,3,4,6；
若按动态规划法求解，所得路径为：1,2,10,6。
例3:设定有n台处理机p1，p2，......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断，作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短
本题不能用贪心算法求解:理由是若n=3,m=6 各作业的时间分别是11 7 5 5 4 7
用贪心策略解(每次将作业加到最先空闲的机器上)time=15,用搜索策略最优时间应是14,但是贪心策略给我们提供了一个线索那就是每台处理上的时间不超过15,给搜索提供了方便。
总之：
1. 不能保证求得的最后解是最佳的；
2. 只能用来求某些最大或最小解问题；
3. 能确定某些问题的可行解的范围，特别是给搜索算法提供了依据。
7. 2 贪心策略的特点
贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：
1、贪心选择性质：
所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。
2、局部最优解：
我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，但贪心策略比动态规划时间效率更高站用内存更少，编写程序更简单。
7.3 典型例题与习题
例4：背包问题：
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30

分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。
程序如下：
program beibao;
const
m=150;
n=7;
var
xu:integer;
i,j:integer;
goods:array[1..n,0..2] of integer;
ok:array[1..n,1..2] of real;
procedure init;
var
i:integer;
begin
xu:=m;
for i:=1 to n do
begin
write('Enter the price and weight of the ',i,'th goods:');
goods[i,0]:=i;
read(goods[i,1],goods[i,2]);
readln;
ok[i,1]:=0; ok[i,2]:=0;
end;
end;
procedure make;
var
bi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
begin
for i:=1 to n do
bi[i]:=goods[i,1]/goods[i,2];
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if bi[i] temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
end;
end;
end;
begin
init;
make;
for i:=1 to 7 do
begin
if goods[i,2]>xu then break;
ok[i,1]:=goods[i,0]; ok[i,2]:=1;
xu:=xu-goods[i,2];
end;
j:=i;
if i<=n then
begin
ok[i,1]:=goods[i,0];
ok[i,2]:=xu/goods[i,2];
end;
for i:=1 to j do
writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
end.
例5：旅行家的预算问题：
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市，给定两个城市间的距离d1，汽车油箱的容量是c，每升汽油能行驶的距离d2，出发时每升汽油的价格是p，沿途加油站数为n（可为0），油站i离出发点的距离是di，每升汽油的价格是pi。
计算结果四舍五入保留小数点后两位，若无法到达目的地输出“No answer"
若输入：
d1=275.6 c=11.9 d2=27.4 p=8 n=2
d[1]=102 p[1]=2.9
d[2]=220 p[2]=2.2
output
26.95
本问题的贪心策略是：找下一个较便宜的油站，根据距离确定加满、不加、加到刚好到该站。
程序如下:
program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil[i-1]^.way>maxway then
begin
init:=false;
exit
end;
init:=true;
end;
procedure buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procedure solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do
begin
inc(j);
s:=s+oil[j]^.way-oil[j-1]^.way
end;
if s<=maxway+zero then
if (oil[i]^.over+zero>=oil[j]^.way-oil[i]^.way) then
oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else
begin
buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
end
else begin
buy(i,maxway-oil[i]^.over);
j:=i+1;
oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);
end;
i:=j;
until i=n;
end;
begin
cost:=0;
if init then begin
solve;
writeln(cost:0:2);
end else writeln('No answer');
end.
例6:n个部件,每个部件必须经过先A后B两道工序。
以知部件i在A,B 机器上的时间分别为ai，bi。如何安排加工顺序，总加工时间最短？
输入：
5
部件 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9
输出：
34
1 5 4 2 3
本问题的贪心策略是A机器上加工短的应优先，B机器上加工短的应靠后。
程序如下：
program workorder;
const maxn=100;
type jd=record
a,b,m,o:integer;
end;
var n,min,i:integer;
c:array[1..maxn] of jd;
order:array[1..maxn] of integer;
procedure init;
var i:integer;
begin
readln(n);
for i:=1 to n do
read(c[i].a);
readln;
for i:=1 to n do
read(c[i].b);
readln;
for i:=1 to n do
begin
if c[i].a c[i].o:=i;
end;
end;
procedure sort;
var i,j,k,t:integer;
temp:jd;
begin
for i:=1 to n-1 do
begin
k:=i;t:=c[i].m;
for j:=i+1 to n do
if c[j].m if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procedure playorder;
var i,s,t:integer;
begin
fillchar(order,sizeof(order),0);
s:=1;
t:=n;
for i:=1 to n do
if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end
else begin order[t]:=i;t:=t-1;end;
end;
procedure calc_t;
var i,t1,t2:integer;
begin
t1:=0;t2:=0;
for i:=1 to n do
begin
t1:=t1+c[order[i]].a;
if t2 t2:=t2+c[order[i]].b;
end;
min:=t2;
end;
begin
init;
sort;
playorder;
calc_t;
writeln(min);
for i:=1 to n do
write(c[order[i]].o,' ');
writeln;
end.
习题：
1.最佳浏览路线问题:
某旅游区的街道成网格状（见图），其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路值得浏览得程度，分值从-１００到１００的整数，所有林荫道不打分。所有分值不可能全是负值。
　　例如下图是被打过分的某旅游区的街道图：
　　
　　 图6
阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。
2..删数问题
键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N和S，寻找一种删数规则使得剩下得数字组成的新数最小。动态规划初步
动态规划简介
动态规划是运筹学的一个分支
决多阶段决策过程最优化问题的一种方法。195
年,美国数学家
解决这类问题的“最优化原则
年发表
的名著《动态规划》,该书是动态规划方面的第一本著作。动态规划问世以来,在工农
业生
程技术等许多方面都得到
应用,取得
的效
动态规划
息学竞赛是在90年代初期,它以独特的优点获
题者的青睐
它就成为了信息学竞赛中必不可少
方法
所有的国内和国际信
竞赛
至少有一道动态规划
动态规划
常重要
面,我们先通过两个具体问题认
例1、拦截导弹(NOIP1999
题描述
某国为了防御敌
弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有
缺陷:虽然它的第一发炮弹能
任意的高度,但是以后每一发炮弹都不能高于前一发
度
雷达捕捉到敌国的导弹来袭
统还在试用阶段,所以
统
因此有可能不能拦截所有的导
入导弹
的高度数据是不
0000的正整数,每个数
至
空格),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备
多少套这种导弹拦截系统
输入输出样例
0
0
6(最多能拦截的导弹数
要拦截所有导弹最少要配备的系统数
问题分析
我们先解决第
系统最多能拦多少导弹,跟它最后拦截的导弹高度有很大关系
假设
枚导弹是第i枚时,系统能拦得的最大导弹数。例如,样
果系统拦截的最后一枚
299的话,最多可以拦截第1枚(389)、第
枚(300)、第5枚(299)三枚
最大值就是第一问的答案。关
键是怎样求得a
假设现在已经求得a[1]a
线街校圳的批位味数的2
系统拦截
拦截的导弹高度必
假如最后第二枚
假如倒数第
弹是299
类似地
当然,我们现在求得是以65结尾的最
弹数
因此
取所有
的最
类似地,我们可以假设a[1]a[6]为已知,来求得a
样,a[6]、a[5]、a[4]、a
2]也是类似求法
就
即如果系统拦截的最后1枚
389,则只能拦截第
这样,求解过程可以用下列式子归纳
最后,只需把
的最大值输
这就是第一问的解法,这种解题方法就
称为“动态规划
第二问比较有意
紧接着第
所以很容易受前面的影响,多次采用第
的办法,然后
数,其实这是不对的。要举反
为7的高度序
不上升序列为
多次求最长不上升序列的结果
系
其实
分别击落
所以不能用“动态规划”做,那
的做法又是什么呢
我们的目标是用最
统击落所有导弹
系统之间怎么分配导弹数目则无关紧
面错误的想法正是承袭
套系统尽量多拦截导
思维定势,忽视了最优解
系统拦截数较为平均的
本质上是一种贪心算法,但贪心的策略不对。如果从每套
系统拦截的导弹方面来想行
我们就应该换一个思路,从拦截某个导弹所选的系统
题
我
有系统
瞄准高度必须
犯导弹高度,所
统均无法拦截
就不得不启用新系统。如果已有系统中有
拦截该导弹,我
是应该继续使用
是另起炉灶呢 事实是:无论用哪套系统
截了这枚导弹,那
系统的瞄准高度就等
度,这一点对旧的或新的系统都适用。而新系统能拦截
弹髙度最高,即新系统的性能优于任意一套已使用的系统。既然如此,我们当然应该选择
有的系统。如果
统中有多
拦截
隹高度较高的
系统的“潜力”较
较低的系统则不同
打下的导弹别的系统也能打下
到的导弹却未必是
统所够不到的。所以,当有多个系统供选择时,要选瞄准高
度最低的使用,当然瞄准高度同时也要」
下当前已有系统的各个当前瞄准高度,该数组中实际元素
数就是第二问的解答
[参考程序
ength(line)do(分解
current:=0;(
弹的高度
134

展开更多......

收起↑