A. 数据结构和算法在实际的软件开发中都有哪些
应用太多了。
基本上来说C#是基于面向对象语言，你所定义的所有类/结构体都算是数据结构，而且在.net类库中已经定义中诸多可用的类型以供使用。实际开发中根本就离不开结构与算法。
题主之所以有这样的问题，基本上认识到了很多程序员易犯的一个毛病——理论知识与实际应用中的脱节问题，不少程序员都说自己写程序用不上理论知识，或者是理论无用。我一直认为理论才是真正编程的指导，别说你所学的理论知识了，有时我们必须遵守一些软件活动上的标准/规范/规定。比如ISO29500标准有多少程序员读过或听说过？他实事就是关于openxml的一个国际标准，我们要想达到通用的程序，这些标准还是读一读的好。
扯回你的问题，什么是数据结构，什么是算法？如果你真的狭义理由数据结构，或者只是从课本上例子来说，数据结构被定义成一个只有属性成员的类或结构体才算是数据结构吗？事实上并不是，那么是不是只有链表/栈/队列才算是数据结构呢？可以说这是某些人狭义理解数据结构时的一种常规定势思维，但事实上来说，类或结构是数据结构的基本，否则你链表存在的实体到底是什么东西？所以数据结构包含着基本结构与狭义上的顺序表/链表/栈/队等存在实体的集体。为什么我说数据结构在实际运用中广泛体现呢？就数据结构而言，课本上只是为了讲明白结构而已，弱化了其中实体的真正含义，而且不语言的具体实现亦不尽相同，所以他们所讲的数据结构是基本理论的。
我来个例子：链表（C#语言）
publicclassMember
{
publicstringName{get;set;}
publicstringResponsibility{get;set;}
publicstringPosotion{get;set;}
}
publicclassMemberNode
{
publicMemberMember{get;set;}
publicMemberNext{get;set;}
}
//Node其他就是链表中的一个结点结构，这个结点结构除了指明当前的Member之下还指向下Next的下一个结构结构，它最终可以形成一个链表。这就是定义的一个链表。
从以上例子上你可以看出这是一个类似于课本的标准定义，但事实上在C#语法中存在泛型的特点，那么这类似的结构我们不须要一个个地定义了！所以在不同的语言中为了方便编程者，我们甚至可以把这样的结构进行简单化，从而达到一种最简单的使用方式。以C#为例，我们可以使用Node<T>来表示链表/List<T>表示顺序表/Stack<T>表旅亮绝示栈/Queue<T>表示队列，在这种情况下，我们只需要定义我们的泛型即可，结构链之类的本身使用泛型已经在类库中实现了——虽然你不用定义，但不代表不使用或者不用理解这其中的知识。而在课本讲理论的时候，他不可能附带泛型来讲的，所以很多人认为自己去定义数据结构才行，那才是“真正”的数据结构，其实不然。以链表为例，我们需要一个节点除了其实体意义之外，还存在指向下一结点的指针（其实是地址引用）才算是数据结构。根据课本，他们必须这么定义（C#）：
publicclassMemberNode
{
publicstringName{get;set;}
publicstringResponsibility{get;set;}
publicstringPosition{get;set;}
publicMemberNodeNext{get;set;}
}
//死读书的只会承认这种才是真正的数据结构吧（链表节点）
事实上，链表讲的只是一种形式，能最终形成的一种组织数据结构的形式。这个代码会导致我们出现一种极大的误解——每个类型的结构都需要重新定义一次。如果有多个类型结构的话，我们会出现多个不同的定义，这会导致将来类的定义越来越多，对于维护上来说是比较麻烦的。由于设计模式/面向切片等各种开发方式的介入，我们会使用相对比较简单的形式。所以才会有我定义两个类的进步，而后可以出现泛型的更进一步。
你可以这样理解，这种课本上的结构，会导致我们造成每种拆姿结构基本上都需要重新定义一次，我最开始给出的例子键昌可以使用继承的方式，实现某个基类的数据结构（下面的似乎也行，但在使用中可能会出现部分问题），而Node<T>则从根本上解决了这个问题，可以支撑多种类型。
所以此时在理解数据结构时，比如Node<T>，他不旦要求理解链表的节点，还要理解T泛型，那么在数据结构上来说，它指的不再是单一的节点结构，还在包括一个基础的类型。
换句话来说，你在C#等语言中已经不需要再做类似的定义了，只需要定义其基本结构类型即可。但课本上在讲知识的时候，它不可能只针对面向对象或支持泛型的语言来讲，若不支持泛型时，我们必须使用课本上或我最开始写的例子中的形式，若不支持继承的面向过程语言，那么课本上的知识就是硬性的规定，你必须以这种形式来说，而引用则使用指针引用的方式（面向对象的引用其实是一种引用型引用，也就是址引用或称地址引用，与指针类似）。
相信讲到这里你能明白，数据结构在不同的语言中只是变了个形而已，并不是必须是存在指针的才是，也不是只说表面上的那点东西。早期教程都是以fortain语言为主的，而且课本的目的是讲清道理，而不是一种规定。死读书的人以为用不到数据结构，其实他们一直在使用。
再来说一下算法，算法是什么？是解决问题的一种模式，比如解二元一次方程等等，所以算法的定义其实已经告诉你，顺序代码他也算是一种算法，不能说只有背包问题，八皇后问题，回溯问题才算是算法——你能明白吗？其实你正常写的就是一种算法，这种算法简单，就是顺序执行下来就可以了，他也是一种算法的，就算解二元一次方程组有固定的模式（算法），但不代表加减法就不是算法了！所以算法也是常用的东西，那么你学习的算法其实算是开辟思路的一种而已。算法自身的概念已经决定，基本上程序都是由结构与算法构成。我也来举个例子，怎么判断某个链表是否为循环链表？是你的回溯算法，贪心算法还是背包算法？它们只是在解决一些典型问题的一种通用方式而已，很显然，我的问题不是这种典型问题，但不代表他不典型，我们正常的算法是设计两个变量等于头元素，然后开始进入循环，一个变量每次向下推一，即找到他下一个节点，而另一个变量每次找到其孙节点，就算当于两个变量一个每次向下推进一次，而另一个每点推进两次（如果可能），如果不是循环链表，则进两次的那个会在链表总长度的一半时，遇到空引用，否则会在某一时间两指针引用同一对象（不是对象相等，而是引用相同的对象），什么意思呢，好象两个人在圆型跑道上跑步，一个每秒1米，另一个每秒2米，同时同地同向出发，最归跑得快的那个会追上跑得慢的那个！当然这种情况下你也可以给他起个名字，叫“追及算法”？如果只有你学的那几个典型算法是算法的话，这个算不算算法？
现在我们的问题是，如果语言层面上已经实现了这些东西，那么这些理论我们是否可以不用理解就可以了？答案是可以——如果你只是一个不思进取的程序员或允许bug乱飞的没有责任心的编程人员的话，可以不用理解——毕竟有些人只是“混”饭吃而已！
理解了不会去应用，这就是典型的理论联系不到实际，他们也不知道自己的代码将如何控制。我举一个例子，由于性能等各方面的要求，我们要使用多线程对某些数据进行处理。怎么处理？不好人会使用多线程——他们定义一个临界资源，然后让多个线程在读取数据表(DataSet)时进行阻塞，然后每个线程去处理那些超时长的问题，处理完的时个再按这种方式读取数据——这样有问题吗？没有，这也算是算法的一种！反正如果编程代码有功底的话没有任何问题的，这种代码算不算优雅呢——很多人认为代码的优雅就是代码编写过程的形式或是良好的编程习惯！这里边其实用不到数据结构与算法的。
好吧，我承认，但如果我们换一句思路来看看，如果我用一个线程负责读取数据，并不停地放入到一个队列中，而多个线程从队列中不停地读取处理这些放入的数据，这样如何？我的意思是说，并没有直接在DataSet中处理，而是选择使用队列的方式。
我们看一个问题，这个队列Queue<T>，一个线程用来插入数据，多个线程用来读取数据，而且要保证不能重复，那么我们可以使用队列的安全版本（CorrentQueue<T>,在.net中如果非线程安全的情况下，多线程使用实应该找到其对应的安全版本或者控制线程安全)。
插入线程如果发现队列中的长度（容量）较大时，可以暂缓插入。这样可以保证队列的长度基本固定，占用内存得到控制（不是DataSet批量读来一大堆），由于使用安全队列，所以各线程不用考虑线程之间的安全问题，每个线程从队中获得数据并删除，可以保证数据只被处理一次。当然还可以考虑优雅的通知机制，插入线程在插入数据时通知处理线程启动，如果插入速度过快，发现插入数量达指定的长度（比如30个），停止插入，插入线程阻塞；处理处理再次处理时可通知插入线程再进行插入。
这也算是一种算法吧？它可以让插入线程与处理线程同时工作，而使用DataSet那种常规的结果时，只能是等待处理完或加入多个控制条件进行控制，既然这么控制的话，何不直接使用队列的方式？CorrentQueue<T>中的T也完全可以是一条记录DataRow嘛！
如果你认为第一种是你经常使用方式，那么算法对于你来说学与不学无所谓的，你必须使用自己的编程/调试功底以保证你的代码尽量很少出错或不出错。而如果你认为第二种方案优雅一些的话，那么你会认为你学习的算法与结构还是有用的，理论与实践结合了。
我之所以举这么一个例子，其实告诉你的无非是几点非常重要的信息：
你有选择算法的自由（只不过是代码质量、后期维护的问题）
如果你知道的较多的算法与结构，你会有更多的选择。
算法或结构在实际使用中，所谓的典型问题并不是使用场景和书上描述一模一样（试想一下，我第二种考虑的例子中，是不是跟书上比他不典型？其实也是非常典型的）
分析问题时，应该拿要点，而不是整体去套。（如果整体去套用的话，你肯定会想不到使用哪种结构或算法）
不管是数据结构/算法/设计模式都要求是灵活运用，而不是场景对比使用，也不是生搬硬套。
试想一下，你的背包问题，怎么可能公司也让你分拆包装？你的八皇后问题公司恰好让你下棋？你的贪心算法公司恰好让你找零钱？你的回溯算法公司恰好让你走迷宫？学不能致用的原因就是太死板——这几个举个例子的场景你再遇到或理能遇到的机率是非常小的，所以如果觉得学了没用，那就真没用了——只不过不是算法没用，而是人没人！
讲个小故事：从前一个家人的板凳坏了，要找一个合适的两股叉的树杈重新制做一个板凳腿，让孩子到树园里找了半天，孩子回来说“我都没见过有向下叉的树杈！他老爹气得要死——怎么会可能有向下长的树杈呢！这孩子是不是笨——你就不会把地刨了找一个向下分叉的树根！
算法也是一样，迷宫找路可以使用回溯算法，但不是所有的回溯算法都用于迷宫找路——它还可以用来设计迷宫！嘿嘿嘿！
B. 算法有哪些分类
算法可以分为多种类型，包括但不限于：
1. 基本算法：这些是算法设计的基石，包括了各种基本的操作和指令。
2. 数据结构的算法：涉及特定数据结构的操作和优化，如链表、树、图等。
3. 数论与代数算法：专注于数学领域，如素数生成、最大公约数计算等。
4. 计算几何的算法：处理几何形状和空间的计算问题，如点到点的距离计算、凸包问题等。
5. 图论的算法：解决图相关的问题，如最短路径查找、网络流计算等。
6. 动态规划：解决可以通过分割问题来递归解决的问题，如背包问题、最长公共子序列等。
7. 数值分析：处理数值计算问题，如数值积分、数值微分等。
8. 加密算法：用于数据安全和隐私保护，如对称加密、非对称加密等。
9. 排序算法：对数据进行排序，如快速排序、归并排序等。
10. 检索算法：从大量数据中查找特定信息，如二分查找、B树查找等。
11. 随机化算法：使用随机数来解决计算问题，以提高效率或解决特定问题。
12. 并行算法：设计用于并行计算的算法，以提高处理大规模问题的速度。
13. 机器学习算法：根据数据训练模型，如监督学习、非监督学习和半监督学习算法。
14. 哈夫曼编码、树的遍历、最短路径算法等特定于图论的算法。
请注意，算法的分类不是固定不变的，随着技术的发展和新问题的出现，可能会有新的算法类型被提出。
C. PASCAL算法知识题~~高分~紧急~
6.1 穷举策略的概念
所谓枚举法，指的是从可能的解的集合中一一枚举各元素， 用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。
有些问题可以用循环语句和条件语句直接求解，有些问题用循环求解时循环次数太多，无法编写程序，怎么办？下面是用“千军万马过独木桥，适者存”的方式实现穷举策略的。
6.2 典型例题与习题
例1.将2n个0和2n个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2n+1个二进制数都不相同。
例如，当n=2时，即22个0和22个1排成如下一圈：
比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，...可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。
程序说明：
以n=4为例，即有16个0，16个1，数组a用以记录32个0，1的排法，数组b统计二进制数出现的可能性。
程序清单
PROGRAM NOI00;
VAR
A :ARRAY[1..36] OF 0..1
B :ARRAY[0..31] OF INTEGER;
I,J,K,S,P:INTEGER;
BEGIN
FOR I:=1 TO 36 DO A[I]:=0;
FOR I:=28 TO 32 DO A[I]:=1;
P:=1; A[6]:=1;
WHILE (P=1) DO
BEGIN
J:=27
WHILE A[J]=1 DO J:=J-1;
( A[J]:=1 )
FOR I:=J+1 TO 27 DO ( A[i]:=0 )
FOR I:=0 TO 31 DO B[I]:=0;
FOR I:=1 TO 32 DO
BEGIN
( S:=0)
FOR K:=I TO I+4 DO S:=S*2+A[k];
( B[S]:=1 )
END;
S:=0;
FOR I:=0 TO 31 DO S:=S+B[I];
IF ( S=32 ) THEN P:=0
END;
FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]);
WRITELN
END.
例2：在A、B两个城市之间设有N个路站(如下图中的S1，且N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数<=20，且每条路段上的距离均为一个整数)。
A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(最大距离<=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。
例如：下图所示是当N=1时的情况：
从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。
算法说明：本题采用穷举算法。
数据结构：N：记录A，B间路站的个数
数组D[I，0]记录第I-1个到第I路站间路段的个数
D[I，1]，D[I，2]，…记录每个路段距离
数组G记录可取到的距离
程序清单：
program CHU7_6;
var i,j,n,s:integer;
b:array[0..100] of integer;
d:array[0..100,0..20] of integer;
g:array[0..1000] of 0..1;
begin
readln(n);
for i:=1 to n+1 do
begin
readln(d[i,0]);
for j:=1 to d[i,0] do read(d[i,j]);
end;
d[0,0]:=1;
for i:=1 to n+1 do b[i]:=1;
b[0]:=0;
for i:=1 to 1000 do g[i]:=0;
while b[0]<>1 do
begin
s:=0;
for i:=1 to n+1 do
s:= s+d[i,b[i]];
g[s]:=1;j:=n+1;
while b[j]=d[j,0] do j:=j-1;
b[j]:=b[j]+1;
for i:=j+1 to n+1 do b[i]:=1;
end;
s:=0;
for i:=1 to 1000 do
s:=s+g[i];
writeln(s);readln;
end.
2.1 递归的概念
1.概念
一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).
如:
procere a;
begin
.
.
.
a;
.
.
.
end;
这种方式是直接调用.
又如:
procere b; procere c;
begin begin
. .
. .
. .
c; b;
. .
. .
. .
end; end;
这种方式是间接调用.
例1计算n!可用递归公式如下:
1 当 n=0 时
fac(n)={n*fac(n-1) 当n>0时
可编写程序如下:
program fac2;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)
end;
begin
write('n=');readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.
例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.
设n阶台阶的走法数为f(n)
显然有
1 n=1
f(n)={2 n=2
f(n-1)+f(n-2) n>2
可编程序如下：
program louti;
var n:integer;
function f(x:integer):integer;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
2.2 如何设计递归算法
1.确定递归公式
2.确定边界(终了)条件
练习:
用递归的方法完成下列问题
1.求数组中的最大数
2.1+2+3+...+n
3.求n个整数的积
4.求n个整数的平均值
5.求n个自然数的最大公约数与最小公倍数
6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
2.3典型例题
例3 梵塔问题
如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子
从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上
不能出现大盘压小盘.找出移动次数最小的方案.
程序如下:
program fanta;
var
n:integer;
procere move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'--->',c)
else begin
move(n-1,a,c,b);
writeln(a,'--->',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=');
read(n);
move(n,1,2,3);
end.
例4 快速排序
快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.
程序如下:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
3.1 回溯的设计
1.用栈保存好前进中的某些状态.
2.制定好约束条件
例1由键盘上输入任意n个符号;输出它的全排列.
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
例2.n个皇后问题:
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
回溯算法的公式如下:
3.2 回溯算法的递归实现
由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。
上述例1的递归方法实现如下：
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procere try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.
例2：n皇后问题的递归算法如下：
程序1：
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.
程序2：
说明:当n=8 时有30条对角线分别用了l和r数组控制，
用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:
program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.
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;
procere 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;
procere 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]<bi[j] then begin
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;
procere buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procere 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;
procere 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].b then c[i].m:=c[i].a else c[i].m:=c[i].b;
c[i].o:=i;
end;
end;
procere 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<t then begin t:=c[j].m;k:=j end ;
if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procere 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;
procere 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<t1 then t2:=t1;
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.
D. 关于NOIP
NOIP级别中，普及组和提高组的要求不同。
但是这几类动规的题目掌握了，基本也就可以了：
1、背包问题：01背包、完全背包、需要构造的多维01背包
详见背包九讲
2、最大降序：例如打导弹
3、矩阵相乘：例如能量珠子
4、买股票
5、方格取数：单向的、双向的
6、三角取数
这些都是简单的动规的应用，必须掌握，背也要背出来，还要会套用。
至于排序，本人认为基本的选择排序大家都会，快速排序是一定要会的，当数据规模<500时用选择排序，当数据规模在500和100000之间是用快速排序，但是NOIP中经常考到基数排序，例如划分数线等，数据规模会达到1000000，用其他的排序法可能会超时一两个测试点。
至于搜索，那是必须掌握的深搜、广搜都要会，主要是深搜，当提高组碰到一下子想不出动规的状态转移方程式，深搜穷举也是可行的，一般都能拿到不少的分数。个人之间广搜的用处不大，程序复杂而且爆机率很高。当然n个for的穷举法在不得已的时候也能得不少分，只要if剪枝的好，对付八后问题等问题时，时间效率比很高。
另外就是图的遍历，有关图的最小生成树、图的单源最短路径，也是需要很好地掌握，一直会考。当然，深搜的本事高的人可以用深搜搞定。
总结如下：要得一等，必须对模拟法和穷举法有深刻的体会，并知道很多变通的手段；对快排要背的滚瓜烂熟；对深搜要做到不管是贪心还是动规的题，都能用深搜实现，只不过少量点超时而已；动规要记住六大模型，然后背包要理解透彻；数学很重要，数学分析的题要做对，例如排组合、凸包、计算几何近几年常考。有了这些，一等可以稳拿。
E. 分别用队列和优先级队列分支限界法解0—1背包问题
利用优先级分支限界法设计0/1背包问题的算法，掌握分支限界法的基本思想和算法设计的基本步骤，注意其中结点优先级的确定方法，要有利于找到最优解的启发信息。
要求：设计0/1背包问题的分支限界算法，利用c语言（c++语言）实现算法，给出程序的正确运行结果。
注意：
1. 把物品按照单位体积的价值降序排列；
2. 构造优先级分支限界法的状态空间树，共n层，第i层每个节点的两个分支分别代表第i个物品的取和不取；
3. 节点上需要保存的值有：S代表已装入背包的物品的总体积，V代表已装入背包的物品的总价值，u代表当前节点的上界，计算公式如下：
u=V+（C-S）（vi+1/si+1）
其中C是背包的总容积，vi+1代表第i+1个物品的价值，si+1代表第i+1个物品的体积。
4. 选择适当的数据结构（如最大堆，或者基本的线性数组）实现算法，输出最后结果。