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. 選擇適當的數據結構（如最大堆，或者基本的線性數組）實現演算法，輸出最後結果。