在众多的计算机解题策略中，贪心策略可以算得上是最接近人们日常思维的一种解题策略，正基于此，贪心策略在各级各类信息学竞赛、尤其在对npc类问题的求解中发挥着越来越重要的作用。
7.1 贪心策略的定义
贪心策略是：指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。
其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
例1：在n行m列的正整数矩阵中，要求从每一行中选一个数，使得选出的n个数的和最大。
本题可用贪心策略：选n次，每一次选相应行中的最大值即可。
例2：在一个n×m的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。
本题用贪心策略不能得到最优解，我们以2×4的矩阵为例。
若按贪心策略求解，所得路径为：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个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
分析：目标函数： ∑pi最大。
约束条件是装入的物品总重量不超过背包容量：∑wi<=m( m=150)
1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
2）每次挑选所占空间最小的物品装入是否能得到最优解？
3）每次选取单位容量价值最大的物品，成为解本题的策略。
程序如下：
program beibao;
constm=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;
vari:integer;
beginxu:=m;
for i:=1 to n do
beginwrite('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;
varbi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
beginfor 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
beginif bi[i]begin
init;make;
for i:=1 to 7 do
beginif 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
beginok[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
本问题的贪心策略是：找下一个较便宜的油站，根据距离确定加满、不加、加到刚好到该站。
程序如下：
program jiayou;
const maxn=10001;
zero=1e-16;
typejd=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;
beginnew(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
beginnew(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
begininit:=false;
exitend;
init:=true;
end;procedure buy(i:integer;miles:real);
begincost:=cost+miles/d2*oil[i]^.value;
end;procedure solve;
var i,j:integer;
s:real;
begini:=1;j:=i+1;
repeat
s:=0.0;
while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do
begininc(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
beginbuy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
endelse 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。如何安排加工顺序，总加工时间最短？ 输入：
输出：本问题的贪心策略是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;
beginreadln(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
beginif c[i].ai then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;end;
procedure playorder;
var i,s,t:integer;
beginfillchar(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;
begint1:=0;t2:=0;
for i:=1 to n do
begint1:=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 掌握贪心算法的基本概念和两个基本要素。2 熟练掌握贪心算法解决问题的基本步骤。3 学会利用贪心算法解决实际问题。二 实验内容 问题描述 题目一 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪... 答案 d 解析 二分法求方程零点的算法中，仅能求方程的一些特殊的近似零点 满足函数零点存在性定理的条件 则d正确 6 下列算法要解决的问题是 第一步，比较a与b的大小，如果a b，则交换a，b的值 第二步，比较a与c的大小，如果a c，则交换a，c的值 第三步，比较b与c的大小，如果b c，则交换b... 高中谋改研究。泼践探斜。发挥着越来越大的作用，并日益融入社会生活的许多。算法研读的初步体会。一。不哭自。算。法思想已经成为现尊人应具备铲种数学素。那么怎样理解算法思想呢？笔者认为，算法思想是探求解决问题的一般性方法。是贯穿高中数学课程始终的基本思想。算法是培养学生逻辑思维的最佳教学资源之一，为发展学...实验二贪心算法 最少活动会场安排问题
01算法初步算法的概念
算法研读的初步体会