取得總價值最大演算法題

A. 貪心演算法幾個經典例子

[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。

要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。

貪心演算法是很常見的演算法之一，這是由於它簡單易行，構造貪心策略簡單。但是，它需要證明後才能真正運用到題目的演算法中。一般來說，貪心演算法的證明圍繞著整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。

對於本例題中的3種貪心策略，都無法成立，即無法被證明。

B. Pascal貪心演算法，求解答！

這道題用貪心不大好吧
記得老師以前說過
這種題用DP
這道題是最簡單的01背包
我給你發個資料
那個，發不了啊，上傳失敗
你給我qq吧
P01: 01背包問題
題目
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路
這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f [i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。

注意f[i][v]有意義當且僅當存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢後，最終的答案並不一定是f[N] [V]，而是f[N][0..V]的最大值。如果將狀態的定義中的「恰」字去掉，在轉移方程中就要再加入一項f[i][v-1]，這樣就可以保證f[N] [V]就是最後的答案。至於為什麼這樣就可以，由你自己來體會了。

優化空間復雜度
以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。

先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果只用一個數組f [0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態f[i -1][v-c[i]]的值。偽代碼如下：

for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當於我們的轉移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因為現在的f[v-c[i]]就相當於原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數組解01背包問題是十分必要的。

總結
01背包問題是最基本的背包問題，它包含了背包問題中設計狀態、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及最後怎樣優化的空間復雜度。

P02: 完全背包問題
題目
有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路
這個問題非常類似於01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已並非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態轉移方程，像這樣：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}。這跟01背包問題一樣有O(N*V)個狀態需要求解，但求解每個狀態的時間則不是常數了，求解狀態f[i][v]的時間是O(v/c[i])，總的復雜度是超過O(VN)的。

將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復雜度。

一個簡單有效的優化
完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個優化的正確性顯然：任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對於隨機生成的數據，這個方法往往會大大減少物品的件數，從而加快速度。然而這個並不能改善最壞情況的復雜度，因為有可能特別設計的數據可以一件物品也去不掉。

轉化為01背包問題求解
既然01背包問題是最基本的背包問題，那麼我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c [i]件，於是可以把第i種物品轉化為V/c[i]件費用及價值均不變的物品，然後求解這個01背包問題。這樣完全沒有改進基本思路的時間復雜度，但這畢竟給了我們將完全背包問題轉化為01背包問題的思路：將一種物品拆成多件物品。

更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<V。這是二進制的思想，因為不管最優策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log(V/c[i]))件物品，是一個很大的改進。 但我們有更優的O(VN)的演算法。 * O(VN)的演算法 這個演算法使用一維數組，先看偽代碼： <pre class"example"> for i=1..N for v=0..Vf[v]=max{f[v],f[v-c[i]]+w[i]};

你會發現，這個偽代碼與P01的偽代碼只有v的循環次序不同而已。為什麼這樣一改就可行呢？首先想想為什麼P01中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][v]是由狀態f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮「選入第i件物品」這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][v-c[i]]。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮「加選一件第i種物品」這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][v-c[i]]，所以就可以並且必須採用v= 0..V的順序循環。這就是這個簡單的程序為何成立的道理。

這個演算法也可以以另外的思路得出。例如，基本思路中的狀態轉移方程可以等價地變形成這種形式：f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}，將這個方程用一維數組實現，便得到了上面的偽代碼。

總結
完全背包問題也是一個相當基礎的背包問題，它有兩個狀態轉移方程，分別在「基本思路」以及「O(VN)的演算法「的小節中給出。希望你能夠對這兩個狀態轉移方程都仔細地體會，不僅記住，也要弄明白它們是怎麼得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態規劃題目都思考其方程的意義以及如何得來，是加深對動態規劃的理解、提高動態規劃功力的好方法。

P03: 多重背包問題
題目
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本演算法
這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可，因為對於第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}。復雜度是O(V*∑n[i])。

轉化為01背包問題
另一種好想好寫的基本方法是轉化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數為∑n[i]的01背包問題，直接求解，復雜度仍然是O(V*∑n[i])。

但是我們期望將它轉化為01背包問題之後能夠像完全背包一樣降低復雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n[i]件——均能等價於取若干件代換以後的物品。另外，取超過n[i]件的策略必不能出現。

方法是：將第i種物品分成若干件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分別為 1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數。例如，如果n[i]為13，就將這種物品分成系數分別為1,2,4,6的四件物品。

分成的這幾件物品的系數和為n[i]，表明不可能取多於n[i]件的第i種物品。另外這種方法也能保證對於0..n[i]間的每一個整數，均可以用若干個系數的和表示，這個證明可以分0..2^k-1和2^k..n[i]兩段來分別討論得出，並不難，希望你自己思考嘗試一下。

這樣就將第i種物品分成了O(log n[i])種物品，將原問題轉化為了復雜度為O(V*∑logn[i])的01背包問題，是很大的改進。

O(VN)的演算法
多重背包問題同樣有O(VN)的演算法。這個演算法基於基本演算法的狀態轉移方程，但應用單調隊列的方法使每個狀態的值可以以均攤O(1)的時間求解。由於用單調隊列優化的DP已超出了NOIP的范圍，故本文不再展開講解。我最初了解到這個方法是在樓天成的「男人八題」幻燈片上。

小結
這里我們看到了將一個演算法的復雜度由O(V*∑n[i])改進到O(V*∑log n[i])的過程，還知道了存在應用超出NOIP范圍的知識的O(VN)演算法。希望你特別注意「拆分物品」的思想和方法，自己證明一下它的正確性，並用盡量簡潔的程序來實現。

P04: 混合三種背包問題
問題
如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數有一個上限（多重背包）。應該怎麼求解呢？

01背包與完全背包的混合
考慮到在P01和P02中最後給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那麼只需在對每個物品應用轉移方程時，根據物品的類別選用順序或逆序的循環即可，復雜度是O(VN)。偽代碼如下：

for i=1..N
if 第i件物品是01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品是完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};

再加上多重背包
如果再加上有的物品最多可以取有限次，那麼原則上也可以給出O(VN)的解法：遇到多重背包類型的物品用單調隊列解即可。但如果不考慮超過NOIP范圍的演算法的話，用P03中將每個這類物品分成O(log n[i])個01背包的物品的方法也已經很優了。

小結
有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經得到了充分的體現。本來01背包、完全背包、多重背包都不是什麼難題，但將它們簡單地組合起來以後就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎扎實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。
P05: 二維費用的背包問題
問題
二維費用的背包問題是指：對於每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對於每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別為a[i]和b[i]。兩種代價可付出的最大值（兩種背包容量）分別為V和U。物品的價值為w[i]。

演算法
費用加了一維，只需狀態也加一維即可。設f[i][v][u]表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。狀態轉移方程就是：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法，可以只使用二維的數組：當每件物品只可以取一次時變數v和u採用順序的循環，當物品有如完全背包問題時採用逆序的循環。當物品有如多重背包問題時拆分物品。

物品總個數的限制
有時，「二維費用」的條件是以這樣一種隱含的方式給出的：最多隻能取M件物品。這事實上相當於每件物品多了一種「件數」的費用，每個物品的件數費用均為1，可以付出的最大件數費用為M。換句話說，設f[v][m]表示付出費用v、最多選m件時可得到的最大價值，則根據物品的類型（01、完全、多重）用不同的方法循環更新，最後在f[0..V][0..M]范圍內尋找答案。

另外，如果要求「恰取M件物品」，則在f[0..V][M]范圍內尋找答案。

小結
事實上，當發現由熟悉的動態規劃題目變形得來的題目時，在原來的狀態中加一緯以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方法。

P06: 分組的背包問題
問題
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

演算法
這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值，則有f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬於第k組}。

使用一維數組的偽代碼如下：

for 所有的組k
for 所有的i屬於組k
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]}

另外，顯然可以對每組中的物品應用P02中「一個簡單有效的優化」。

小結
分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉化為分組的背包問題（例如P07），由分組的背包問題進一步可定義「泛化物品」的概念，十分有利於解題。

P07: 有依賴的背包問題
簡化的問題
這種背包問題的物品間存在某種「依賴」的關系。也就是說，i依賴於j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設沒有某個物品既依賴於別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。

演算法
這個問題由NOIP2006金明的預算方案一題擴展而來。遵從該題的提法，將不依賴於別的物品的物品稱為「主件」，依賴於某主件的物品稱為「附件」。由這個問題的簡化條件可知所有的物品由若干主件和依賴於每個主件的一個附件集合組成。

按照背包問題的一般思路，僅考慮一個主件和它的附件集合。可是，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件後再選擇一個附件，選擇主件後再選擇兩個附件……無法用狀態轉移方程來表示如此多的策略。（事實上，設有n個附件，則策略有2^n+1個，為指數級。）

考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應於P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應於這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉化並不能給出一個好的演算法，因為物品組中的物品還是像原問題的策略一樣多。

再考慮P06中的一句話： 可以對每組中的物品應用P02中「一個簡單有效的優化」。這提示我們，對於一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結果。所以，我們可以對主件i的「附件集合」先進行一次01背包，得到費用依次為0..V-c[i]所有這些值時相應的最大價值f'[0..V-c[i]]。那麼這個主件及它的附件集合相當於V-c[i]+1個物品的物品組，其中費用為c[i]+k的物品的價值為f'[k]+w[i]。也就是說原來指數級的策略中有很多策略都是冗餘的，通過一次01背包後，將主件i轉化為 V-c[i]+1個物品的物品組，就可以直接應用P06的演算法解決問題了。

更一般的問題
更一般的問題是：依賴關系以圖論中「森林」的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多隻依賴於一個物品（只有一個主件）且不出現循環依賴。

解決這個問題仍然可以用將每個主件及其附件集合轉化為物品組的方式。唯一不同的是，由於附件可能還有附件，就不能將每個附件都看作一個一般的01 背包中的物品了。若這個附件也有附件集合，則它必定要被先轉化為物品組，然後用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。

事實上，這是一種樹形DP，其特點是每個父節點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性。這已經觸及到了「泛化物品」的思想。看完P08後，你會發現這個「依賴關系樹」每一個子樹都等價於一件泛化物品，求某節點為根的子樹對應的泛化物品相當於求其所有兒子的對應的泛化物品之和。

小結
NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未得。後來我通過思考發現通過引入「物品組」和「依賴」的概念可以加深對這題的理解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發現一個主件和它的兩個附件等價於一個由四個物品組成的物品組，這便揭示了問題的某種本質。

我想說：失敗不是什麼丟人的事情，從失敗中全無收獲才是。

P08: 泛化物品
定義
考慮這樣一種物品，它並沒有固定的費用和價值，而是它的價值隨著你分配給它的費用而變化。這就是泛化物品的概念。

更嚴格的定義之。在背包容量為V的背包問題中，泛化物品是一個定義域為0..V中的整數的函數h，當分配給它的費用為v時，能得到的價值就是h(v)。

這個定義有一點點抽象，另一種理解是一個泛化物品就是一個數組h[0..V]，給它費用v，可得到價值h[V]。

一個費用為c價值為w的物品，如果它是01背包中的物品，那麼把它看成泛化物品，它就是除了h(c)=w其它函數值都為0的一個函數。如果它是完全背包中的物品，那麼它可以看成這樣一個函數，僅當v被c整除時有h(v)=v/c*w，其它函數值均為0。如果它是多重背包中重復次數最多為n的物品，那麼它對應的泛化物品的函數有h(v)=v/c*w僅當v被c整除且v/c<=n，其它情況函數值均為0。

一個物品組可以看作一個泛化物品h。對於一個0..V中的v，若物品組中不存在費用為v的的物品，則h(v)=0，否則h(v)為所有費用為v的物品的最大價值。P07中每個主件及其附件集合等價於一個物品組，自然也可看作一個泛化物品。

泛化物品的和
如果面對兩個泛化物品h和l，要用給定的費用從這兩個泛化物品中得到最大的價值，怎麼求呢？事實上，對於一個給定的費用v，只需枚舉將這個費用如何分配給兩個泛化物品就可以了。同樣的，對於0..V的每一個整數v，可以求得費用v分配到h和l中的最大價值f(v)。也即f(v)=max{h(k)+l(v-k)|0<=k<=v}。可以看到，f也是一個由泛化物品h和l決定的定義域為0..V的函數，也就是說，f是一個由泛化物品h和 l決定的泛化物品。

由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足f(v)=max{h(k)+l(v-k)|0<=k<=v}，則稱f是h與l的和，即f=h+l。這個運算的時間復雜度是O(V^2)。

泛化物品的定義表明：在一個背包問題中，若將兩個泛化物品代以它們的和，不影響問題的答案。事實上，對於其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設此和為s，則答案就是s[0..V]中的最大值。

背包問題的泛化物品
一個背包問題中，可能會給出很多條件，包括每種物品的費用、價值等屬性，物品之間的分組、依賴等關系等。但肯定能將問題對應於某個泛化物品。也就是說，給定了所有條件以後，就可以對每個非負整數v求得：若背包容量為v，將物品裝入背包可得到的最大價值是多少，這可以認為是定義在非負整數集上的一件泛化物品。這個泛化物品——或者說問題所對應的一個定義域為非負整數的函數——包含了關於問題本身的高度濃縮的信息。一般而言，求得這個泛化物品的一個子域（例如0..V）的值之後，就可以根據這個函數的取值得到背包問題的最終答案。

綜上所述，一般而言，求解背包問題，即求解這個問題所對應的一個函數，即該問題的泛化物品。而求解某個泛化物品的一種方法就是將它表示為若干泛化物品的和然後求之。

小結
本講可以說都是我自己的原創思想。具體來說，是我在學習函數式編程的 Scheme 語言時，用函數編程的眼光審視各類背包問題得出的理論。這一講真的很抽象，也許在「模型的抽象程度」這一方面已經超出了NOIP的要求，所以暫且看不懂也沒關系。相信隨著你的OI之路逐漸延伸，有一天你會理解的。

我想說：「思考」是一個OIer最重要的品質。簡單的問題，深入思考以後，也能發現更多。

P09: 背包問題問法的變化
以上涉及的各種背包問題都是要求在背包容量（費用）的限制下求可以取到的最大價值，但背包問題還有很多種靈活的問法，在這里值得提一下。但是我認為，只要深入理解了求背包問題最大價值的方法，即使問法變化了，也是不難想出演算法的。

例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。這都可以根據具體問題利用前面的方程求出所有狀態的值（f數組）之後得到。

還有，如果要求的是「總價值最小」「總件數最小」，只需簡單的將上面的狀態轉移方程中的max改成min即可。

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. 背包問題的演算法

1)登上演算法
用登山演算法求解背包問題 function []=DengShan(n,G,P,W) %n是背包的個數，G是背包的總容量，P是價值向量，W是物體的重量向量 %n=3;G=20;P=[25,24,15];W2=[18,15,10];%輸入量 W2=W; [Y,I]=sort(-P./W2);W1=[];X=[];X1=[]; for i=1:length(I) W1(i)=W2(I(i)); end W=W1; for i=1:n X(i)=0; RES=G;%背包的剩餘容量 j=1; while W(j)<=RES X(j)=1; RES=RES-W(j); j=j+1; end X(j)=RES/W(j); end for i=1:length(I) X1(I(i))=X(i); end X=X1; disp('裝包的方法是');disp(X);disp(X.*W2);disp('總的價值是：');disp(P*X');

時間復雜度是非指數的

2)遞歸法
先看完全背包問題
一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,
每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max{f(x-i)+c[i]} 當x>=w[i] 1<=i<=n
可使用遞歸法解決問題程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,編程很簡單,但當m較大時,容易超時.
4.2 改進的遞歸法
改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函數的值保存起來,開辟一個
一維數組即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
3)貪婪演算法
改進的背包問題：給定一個超遞增序列和一個背包的容量，然後在超遞增序列中選（只能選一次）或不選每一個數值，使得選中的數值的和正好等於背包的容量。

代碼思路：從最大的元素開始遍歷超遞增序列中的每個元素，若背包還有大於或等於當前元素值的空間，則放入，然後繼續判斷下一個元素；若背包剩餘空間小於當前元素值，則判斷下一個元素
簡單模擬如下：

#define K 10
#define N 10

＃i nclude <stdlib.h>
＃i nclude <conio.h>

void create(long array[],int n,int k)
{/*產生超遞增序列*/
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{/*輸出當前的超遞增序列*/
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}

void beibao(long array[],int cankao[],long value,int count)
{/*背包問題求解*/
int i;
long r=value;
for(i=count-1;i>=0;i--)/*遍歷超遞增序列中的每個元素*/
{
if(r>=array[i])/*如果當前元素還可以放入背包，即背包剩餘空間還大於當前元素*/
{
r=r-array[i];
cankao[i]=1;
}
else/*背包剩餘空間小於當前元素值*/
cankao[i]=0;
}
}

void main()
{
long array[N];
int cankao[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)/*所有已經選中的元素之和*/
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
貪婪演算法的另一種寫法，beibao函數是以前的代碼，用來比較兩種演算法：

#define K 10
#define N 10

＃i nclude <stdlib.h>
＃i nclude <conio.h>

void create(long array[],int n,int k)
{
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}

void beibao(long array[],int cankao[],long value,int count)
{
int i;
long r=value;
for(i=count-1;i>=0;i--)
{
if(r>=array[i])
{
r=r-array[i];
cankao[i]=1;
}
else
cankao[i]=0;
}
}

int beibao1(long array[],int cankao[],long value,int n)
{/*貪婪演算法*/
int i;
long value1=0;
for(i=n-1;i>=0;i--)/*先放大的物體，再考慮小的物體*/
if((value1+array[i])<=value)/*如果當前物體可以放入*/
{
cankao[i]=1;/*1表示放入*/
value1+=array[i];/*背包剩餘容量減少*/
}
else
cankao[i]=0;
if(value1==value)
return 1;
return 0;
}

void main()
{
long array[N];
int cankao[N]={0};
int cankao1[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
printf("\nSecond method:\n");
if(beibao1(array,cankao1,value,N)==1)
{
for(i=0;i<N;i++)
if(cankao1[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}

4)動態規劃演算法

解決0/1背包問題的方法有多種，最常用的有貪婪法和動態規劃法。其中貪婪法無法得到問題的最優解，而動態規劃法都可以得到最優解，下面是用動態規劃法來解決0/1背包問題。

動態規劃演算法與分治法類似，其基本思想是將待求解問題分解成若干個子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的，若用分治法解這類問題，則分解得到的子問題數目太多，以至於最後解決原問題需要耗費過多的時間。動態規劃法又和貪婪演算法有些一樣，在動態規劃中，可將一個問題的解決方案視為一系列決策的結果。不同的是，在貪婪演算法中，每採用一次貪婪准則便做出一個不可撤回的決策，而在動態規劃中，還要考察每個最優決策序列中是否包含一個最優子序列。

0/1背包問題

在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對於可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示選取物品i) 取得最大值。
在該問題中需要決定x1 .. xn的值。假設按i = 1，2，...，n 的次序來確定xi 的值。如果置x1 = 0，則問題轉變為相對於其餘物品(即物品2，3，.，n)，背包容量仍為c 的背包問題。若置x1 = 1，問題就變為關於最大背包容量為c-w1 的問題。現設r?{c，c-w1 } 為剩餘的背包容量。
在第一次決策之後，剩下的問題便是考慮背包容量為r 時的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之後的一個最優方案，如果不是，則會有一個更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一個更好的方案。
假設n=3, w=[100,14,10], p=[20,18,15], c= 116。若設x1 = 1，則在本次決策之後，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因為[x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 並非最優策略。即x= [ 1，0，1] 可改進為x= [ 1，1，0 ]。若設x1 = 0，則對於剩下的兩種物品而言，容量限制條件為116。總之，如果子問題的結果[x2，x3 ]不是剩餘情況下的一個最優解，則[x1，x2，x3 ]也不會是總體的最優解。在此問題中，最優決策序列由最優決策子序列組成。假設f (i,y) 表示剩餘容量為y，剩餘物品為i，i + 1，...，n 時的最優解的值，即：利用最優序列由最優子序列構成的結論，可得到f 的遞歸式為：
當j>=wi時： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式
當0<=j<wi時：f(i,j)=f(i+1,j) ②式
fn( 1 ,c) 是初始時背包問題的最優解。
以本題為例：若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。因此最優解f ( 1 , 11 6 ) = m a x {f(2，11 6)，f(2，11 6 - w1)+ p1} = m a x {f(2，11 6)，f(2，1 6)+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
現在計算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩餘容量c-w1中尋求最優解，用f (2, c-w1) 表示最優解。依此類推，可得到所有的xi (i= 1.n) 值。
在該例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計算x2 及x3，此時r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。

E. 貪心演算法的例題分析

例題1、
[0-1背包問題]有一個背包，背包容量是M=150。有7個物品，物品不可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
價值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目標函數：∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M(M=150）
⑴根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
⑵每次挑選所佔重量最小的物品裝入是否能得到最優解？
⑶每次選取單位重量價值最大的物品，成為解本題的策略。
值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
⑴貪心策略：選取價值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
⑵貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
⑶貪心策略：選取單位重量價值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。
【注意：如果物品可以分割為任意大小，那麼策略3可得最優解】
對於選取單位重量價值最大的物品這個策略，可以再加一條優化的規則：對於單位重量價值一樣的，則優先選擇重量小的！這樣，上面的反例就解決了。
但是，如果題目是如下所示，這個策略就也不行了。
W=40
物品：A B C
重量：25 20 15
價值：25 20 15
附：本題是個DP問題，用貪心法並不一定可以求得最優解，以後了解了動態規劃演算法後本題就有了新的解法。
例題2、
馬踏棋盤的貪心演算法
123041-23 XX
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條路徑。
【初步設計】
首先這是一個搜索問題，運用深度優先搜索進行求解。演算法如下：
⒈ 輸入初始位置坐標x,y；
⒉ 步驟 c:
如果c> 64輸出一個解，返回上一步驟c--
（x,y) ← c
計算(x,y）的八個方位的子結點，選出那些可行的子結點
循環遍歷所有可行子結點，步驟c++重復2
顯然⑵是一個遞歸調用的過程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//輸出一個解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八個方位子結點ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//遞歸調用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8個方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{確定新坐標是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判斷是否走過}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐標}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{遞歸}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{讀入開始坐標}Readln(x1,y1）；{讀入結束坐標}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判斷是否越界}ElseFind(x,y);Writeln('Total:',total){打出總數}END.這樣做是完全可行的，它輸入的是全部解，但是馬遍歷當8×8時解是非常之多的，用天文數字形容也不為過，這樣一來求解的過程就非常慢，並且出一個解也非常慢。
怎麼才能快速地得到部分解呢？
【貪心演算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法，也叫貪婪演算法或啟發式演算法，它對整個求解過程的局部做最優調整，它只適用於求較優解或者部分解，而不能求最優解。這樣的調整方法叫貪心策略，至於什麼問題需要什麼樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個演算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。

F. C語言 貪心演算法求背包問題

是你的冒泡排序出了問題~

你吧 原來的1-2-3號按照東西的價值重新排列現在的1-2-3對應原來的2-1-3了
所以 你輸出的時候是按 1-2-3輸出的話 就等於第一個是原來的X2 第二個是X1第三個是X3
而且你的冒泡排序用錯了 只比較了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去學校幫你重新改改 我家的機器沒有C++
周一晚上我會上傳答案~我最近正好也要做演算法的作業~
#include <stdio.h>
#include <math.h>
#define N 50

float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放單位價值量大的物體，再考慮小的物體*/
{
int i;
float maxprice;
for (i = 0; i < n; i++)
x[i] = 0;
i = 0;
maxprice=0;
while (i < n && w[i] < M)
{
M=M-w[i];
x[i] =w[i]; /* 表示放入數量 */
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if (i < n &&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}

int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(

G. 求NOI的經典題目與演算法。

皇後問題。在一個國際象棋棋盤上，放置8個皇後，使她們相互之間不能進攻(只要在一條直線上就不可，即在每一橫列豎列斜列只有一個皇後）。求出所有布局。
program eight;
var a:array [1..8] of integer;
b,c,d:array [-7..16] of integer;
t,i,j,k:integer;
procere print;
begin
t:=t+1;
write(t,' ');
for k:=1 to 8 do write(a[k],' ');
writeln;
end;

procere try(i:integer);
var j:integer;
begin
for j:=1 to 8 do {每個皇後都有8種可能位置}
if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判斷位置是否沖突}
begin
a[i]:=j; {擺放皇後}
b[j]:=1; {宣布佔領第J行}
c[i+j]:=1; {佔領兩個對角線}
d[i-j]:=1;
if i<8 then try(i+1) {8個皇後沒有擺完，遞歸擺放下一皇後}
else print; {完成任務，列印結果}
b[j]:=0; {回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
for k:=-7 to 16 do {數據初始化}
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);{從第1個皇後開始放置}
end.
這是深搜的內容
搜索資料：
搜 索 算 法
搜索演算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解
的一種方法。搜索過程實際上是根據初始條件和擴展規則構造一棵解答樹並尋找符合目標狀態的節點的過程。
所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分——控制結構和產生系統，而所有的算
法的優化和改進主要都是通過修改其控制結構來完成的。現在主要對其控制結構進行討論，因此對其產生系
統作如下約定：
Function ExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;
表示對給出的節點狀態Sitution採用第ExpendWayNo種擴展規則進行擴展，並且返回擴展後的狀態。
（本文所採用的演算法描述語言為類Pascal。）
第一部分 基本搜索演算法
一、回溯演算法
回溯演算法是所有搜索演算法中最為基本的一種演算法，其採用了一種「走不通就掉頭」思想作為其控制結構，
其相當於採用了先根遍歷的方法來構造解答樹，可用於找解或所有解以及最優解。具體的演算法描述如下：
[非遞歸演算法]
<Type>
Node(節點類型)＝Record
Situtation:TSituation（當前節點狀態）;
Way-NO:Integer（已使用過的擴展規則的數目）;
End
<Var>
List(回溯表):Array[1..Max(最大深度)] of Node;
pos(當前擴展節點編號):Integer;
<Init>
List<-0;
pos<-1;
List[1].Situation<-初始狀態;
<Main Program>
While (pos>0(有路可走)) and ([未達到目標]) do
Begin
If pos>=Max then (數據溢出,跳出主程序);
List[pos].Way-NO:=List[pos].Way-No+1;
If (List[pos].Way-NO<=TotalExpendMethod) then (如果還有沒用過的擴展規則)
Begin
If (可以使用當前擴展規則) then
Begin
(用第way條規則擴展當前節點)
List[pos+1].Situation:=ExpendNode(List[pos].Situation,
List[pos].Way-NO);
List[pos+1].Way-NO:=0;
pos:=pos+1;
End-If;
End-If
Else Begin
pos:=pos-1;
End-Else
End-While;
[遞歸演算法]
Procere BackTrack(Situation:TSituation;deepth:Integer);
Var I :Integer;
Begin
If deepth>Max then (空間達到極限,跳出本過程);
If Situation=Target then (找到目標);
For I:=1 to TotalExpendMethod do
Begin
BackTrack(ExpendNode(Situation,I),deepth+1);
End-For;
End;
範例：一個M*M的棋盤上某一點上有一個馬，要求尋找一條從這一點出發不重復的跳完棋盤上所有的點的路線。
評價：回溯演算法對空間的消耗較少，當其與分枝定界法一起使用時，對於所求解在解答樹中層次較深的問題
有較好的效果。但應避免在後繼節點可能與前繼節點相同的問題中使用，以免產生循環。
二、深度搜索與廣度搜索
深度搜索與廣度搜索的控制結構和產生系統很相似，唯一的區別在於對擴展節點選取上。由於其保留了
所有的前繼節點，所以在產生後繼節點時可以去掉一部分重復的節點，從而提高了搜索效率。這兩種演算法每
次都擴展一個節點的所有子節點，而不同的是，深度搜索下一次擴展的是本次擴展出來的子節點中的一個，
而廣度搜索擴展的則是本次擴展的節點的兄弟節點。在具體實現上為了提高效率,所以採用了不同的數據結構.
[廣度搜索]
<Type>
Node(節點類型)＝Record
Situtation:TSituation（當前節點狀態）;
Level:Integer(當前節點深度);
Last :Integer(父節點);
End
<Var>
List(節點表):Array[1..Max(最多節點數)] of Node(節點類型);
open(總節點數):Integer;
close(待擴展節點編號):Integer;
New-S:TSituation;(新節點)
<Init>
List<-0;
open<-1;
close<-0;
List[1].Situation<- 初始狀態;
List[1].Level:=1;
List[1].Last:=0;
<Main Program>
While (close<open(還有未擴展節點)) and
(open<Max(空間未用完)) and
(未找到目標節點) do
Begin
close:=close+1;
For I:=1 to TotalExpendMethod do（擴展一層子節點）
Begin
New-S:=ExpendNode(List[close].Situation,I);
If Not (New-S in List) then
(擴展出的節點從未出現過)
Begin
open:=open+1;
List[open].Situation:=New-S;
List[open].Level:=List[close].Level+1;
List[open].Last:=close;
End-If
End-For;
End-While;
[深度搜索]
<Var>
Open:Array[1..Max] of Node;(待擴展節點表)
Close:Array[1..Max] of Node;(已擴展節點表)
openL,closeL:Integer;(表的長度)
New-S:Tsituation;(新狀態)
<Init>
Open<-0; Close<-0;
OpenL<-1;CloseL<-0;
Open[1].Situation<- 初始狀態;
Open[1].Level<-1;
Open[1].Last<-0;
<Main Program>
While (openL>0) and (closeL<Max) and (openL<Max) do
Begin
closeL:=closeL+1;
Close[closeL]:=Open[openL];
openL:=openL-1;
For I:=1 to TotalExpendMethod do（擴展一層子節點）
Begin
New-S:=ExpendNode(Close[closeL].Situation,I);
If Not (New-S in List) then
(擴展出的節點從未出現過)
Begin
openL:=openL+1;
Open[openL].Situation:=New-S;
Open[openL].Level:=Close[closeL].Level+1;
Open[openL].Last:=closeL;
End-If
End-For;
End;
範例：迷宮問題，求解最短路徑和可通路徑。
評價：廣度搜索是求解最優解的一種較好的方法，在後面將會對其進行進一步的優化。而深度搜索多用於只
要求解，並且解答樹中的重復節點較多並且重復較難判斷時使用，但往往可以用A*或回溯演算法代替。
第二部分 搜索演算法的優化
一、雙向廣度搜索
廣度搜索雖然可以得到最優解，但是其空間消耗增長太快。但如果從正反兩個方向進行廣度搜索，理想
情況下可以減少二分之一的搜索量，從而提高搜索速度。
範例：有N個黑白棋子排成一派，中間任意兩個位置有兩個連續的空格。每次空格可以與序列中的某兩個棋子
交換位置，且兩子的次序不變。要求出入長度為length的一個初始狀態和一個目標狀態，求出最少的
轉化步數。
問題分析：該題要求求出最少的轉化步數，但如果直接使用廣度搜索，很容易產生數據溢出。但如果從初始
狀態和目標狀態兩個方向同時進行擴展，如果兩棵解答樹在某個節點第一次發生重合，則該節點
所連接的兩條路徑所拼成的路徑就是最優解。
對廣度搜索演算法的改進：
1。添加一張節點表，作為反向擴展表。
2。在while循環體中在正向擴展代碼後加入反向擴展代碼，其擴展過程不能與
正向過程共享一個for循環。
3。在正向擴展出一個節點後，需在反向表中查找是否有重合節點。反向擴展時
與之相同。
對雙向廣度搜索演算法的改進：
略微修改一下控制結構，每次while循環時只擴展正反兩個方向中節點數目較少的一個，可以使兩邊的發
展速度保持一定的平衡，從而減少總擴展節點的個數，加快搜索速度。
二、分支定界
分支定界實際上是A*演算法的一種雛形，其對於每個擴展出來的節點給出一個預期值，如果這個預期值不
如當前已經搜索出來的結果好的話，則將這個節點(包括其子節點)從解答樹中刪去，從而達到加快搜索速度
的目的。
範例：在一個商店中購物，設第I種商品的價格為Ci。但商店提供一種折扣，即給出一組商品的組合，如果一
次性購買了這一組商品，則可以享受較優惠的價格。現在給出一張購買清單和商店所提供的折扣清單，
要求利用這些折扣，使所付款最少。
問題分析：顯然，折扣使用的順序與最終結果無關，所以可以先將所有的折扣按折扣率從大到小排序，然後
採用回溯法的控制結構，對每個折扣從其最大可能使用次數向零遞減搜索，設A為以打完折扣後優
惠的價格，C為當前未打折扣的商品零售價之和，則其預期值為A+a*C，其中a為下一個折扣的折扣
率。如當前已是最後一個折扣，則a=1。
對回溯演算法的改進：
1。添加一個全局變數BestAnswer，記錄當前最優解。
2。在每次生成一個節點時，計算其預期值，並與BestAnswer比較。如果不好，則調用回溯過程。
三、A*演算法
A*演算法中更一般的引入了一個估價函數f,其定義為f=g+h。其中g為到達當前節點的耗費，而h表示對從當
前節點到達目標節點的耗費的估計。其必須滿足兩個條件：
1。h必須小於等於實際的從當前節點到達目標節點的最小耗費h*。
2。f必須保持單調遞增。

A*演算法的控制結構與廣度搜索的十分類似，只是每次擴展的都是當前待擴展節點中f值最小的一個，如果
擴展出來的節點與已擴展的節點重復，則刪去這個節點。如果與待擴展節點重復，如果這個節點的估價函數
值較小，則用其代替原待擴展節點，具體演算法描述如下：
範例：一個3*3的棋盤中有1-8八個數字和一個空格，現給出一個初始態和一個目標態，要求利用這個空格，
用最少的步數，使其到達目標態。
問題分析：預期值定義為h=|x-dx|+|y-dy|。
估價函數定義為f=g+h。
<Type>
Node(節點類型)＝Record
Situtation:TSituation（當前節點狀態）;
g:Integer;(到達當前狀態的耗費)
h:Integer;(預計的耗費)
f:Real;(估價函數值)
Last:Integer;(父節點)
End
<Var>
List(節點表):Array[1..Max(最多節點數)] of Node(節點類型);
open(總節點數):Integer;
close(待擴展節點編號):Integer;
New-S:Tsituation;(新節點)
<Init>
List<-0;
open<-1;
close<-0;
List[1].Situation<- 初始狀態;
<Main Program>
While (close<open(還有未擴展節點)) and
(open<Max(空間未用完)) and
(未找到目標節點) do
Begin
Begin
close:=close+1;
For I:=close+1 to open do (尋找估價函數值最小的節點)
Begin
if List.f<List[close].f then
Begin
交換List和List[close];
End-If;
End-For;
End;
For I:=1 to TotalExpendMethod do（擴展一層子節點）
Begin
New-S:=ExpendNode(List[close].Situation,I)
If Not (New-S in List[1..close]) then
(擴展出的節點未與已擴展的節點重復)
Begin
If Not (New-S in List[close+1..open]) then
(擴展出的節點未與待擴展的節點重復)
Begin
open:=open+1;
List[open].Situation:=New-S;
List[open].Last:=close;
List[open].g:=List[close].g+cost;
List[open].h:=GetH(List[open].Situation);
List[open].f:=List[open].h+List[open].g;
End-If
Else Begin
If List[close].g+cost+GetH(New-S)<List[same].f then
(擴展出來的節點的估價函數值小於與其相同的節點)
Begin
List[same].Situation:= New-S;
List[same].Last:=close;
List[same].g:=List[close].g+cost;
List[same].h:=GetH(List[open].Situation);
List[same].f:=List[open].h+List[open].g;
End-If;
End-Else;
End-If
End-For;
End-While;
對A*演算法的改進--分階段A*：
當A*演算法出現數據溢出時，從待擴展節點中取出若干個估價函數值較小的節點，然後放棄其餘的待擴展
節點，從而可以使搜索進一步的進行下去。
第三部分 搜索與動態規劃的結合
例1. 有一個棋子，其1、6面2、4面3、5面相對。現給出一個M*N的棋盤，棋子起初處於(1,1)點，擺放狀態
給定，現在要求用最少的步數從(1,1)點翻滾到(M,N)點，並且1面向上。
分析：這道題目用簡單的搜索很容易發生超時，特別當M、N較大時。所以可以考慮使用動態規劃來解題。對
於一個棋子，其總共只有24種狀態。在(1,1)點時，其向右翻滾至(2,1)點，向上翻滾至(1,2)點。而
任意（I，J）點的狀態是由（I-1，J）和（I，J-1）點狀態推導出來的。所以如果規定棋子只能向上
和向右翻滾，則可以用動態規劃的方法將到達（M，N）點的所有可能的狀態推導出來。顯然，從（1，
1）到達（N，M）這些狀態的路徑時最優的。如果這些狀態中有1面向上的，則已求出解。如果沒有，
則可以從（M，N）點開始廣度搜索，以（M，N）點的狀態組作為初始狀態，每擴展一步時，檢查當前
所得的狀態組是否有狀態與到達格子的狀態組中的狀態相同，如果有，則由動態規劃的最優性和廣度
搜索的最優性可以保證已求出最優解。
例2.給出一個正整數n，有基本元素a，要求通過最少次數的乘法，求出a^n。
分析：思路一：這道題從題面上來看非常象一道動態規劃題，a^n=a^x1*a^x2。在保證a^x1和a^x2的最優性之
後，a^n的最優性應該得到保證。但是仔細分析後可以發現，a^x1與a^x2的乘法過程中可能有
一部分的重復，所以在計算a^n時要減去其重復部分。由於重復部分的計算較繁瑣，所以可以
將其化為一組展開計算。描述如下：
I:=n;(拆分a^n)
split[n]:=x1;(分解方案)
Used[n]:=True;(在乘法過程中出現的數字)
Repeat(不斷分解數字)
Used[I-split[I]]:=True;
Used[split[I]]:=True;
Dec(I);
While (I>1) and (not Used[I]) do dec(I);
Until I=1;
For I:=n downto 1 do(計算總的乘法次數)
If Used[I] then count:=count+1;
Result:=count;(返回乘法次數)
思路二：通過對思路一的輸出結果的分析可以發現一個規律：
a^19=a^1*a^18
a^18=a^2*a^16
a^16=a^8*a^8
a^8=a^4*a^4
a^4=a^2*a^2
a^2=a*a
對於一個n，先構造一個最接近的2^k，然後利用在構造過程中產生的2^I,對n-2^k進行二進制分解，
可以得出解。對次數的計算的描述如下：
count:=0;
Repeat
If n mod 2 = 0 then count:=count+1
Else count:=count+2;
n:=n div 2;
Until n=1;
Result:=count;
反思：觀察下列數據：
a^15 a^23 a^27
Cost:5 Cost:6 Cost:6
a^2=a^1*a^1 a^2=a^1*a^1 a^2=a^1*a^1
a^3=a^1*a^2 a^3=a^1*a^2 a^3=a^1*a^2
a^6=a^3*a^3 a^5=a^2*a^3 a^6=a^3*a^3
a^12=a^6*a^6 a^10=a^5*a^5 a^12=a^6*a^6
a^15=a^3*a^12 a^20=a^10*a^10 a^24=a^12*a^12
a^23=a^3*a^20 a^27=a^3*a^24
這些數據都沒有採用思路二種的分解方法，而都優於思路二中所給出的解。但是經過實測，思路一二
的所有的解的情況相同，而卻得不出以上數據中的解。經過對a^2－a^15的數據的完全分析，發現對於
一個a^n，存在多個分解方法都可以得出最優解，而在思路一中只保留了一組分解方式。例如對於a^6
只保留了a^2*a^4，從而使a^3*a^3這條路中斷，以至採用思路一的演算法時無法得出正確的耗費值，從
而丟失了最優解。所以在計算a^n=a^x1*a^x2的重復時，要引入一個搜索過程。例如:a^15=a^3*a^12，
a^12=a^6*a^6，而a^6=a^3*a^3。如果採用了a^6=a^2*a^4，則必須多用一步。
<Type>
Link=^Node; （使用鏈表結構紀錄所有的可能解）
Node=Record
split:Integer;
next :Link;
End;
<Var>
Solution:Array[1..1000] of Link; （對於a^n的所有可能解）
Cost :Array[1..1000] of Integer; （解的代價）
max :Integer; （推算的上界）
<Main Program>
Procere GetSolution;
Var i,j :Integer;
min,c:Integer;
count:Integer;
temp,tail:Link;
plan :Array[1..500] of Integer;
nUsed:Array[1..1000] of Boolean;
Procere GetCost(From,Cost:Integer); （搜索計算最優解）
Var temp:Link;
a,b :Boolean;
i :Integer;
Begin
If Cost>c then Exit; （剪枝）
If From=1 then （遞歸終結條件）
Begin
If Cost<c then c:=Cost;
Exit;
End;
temp:=Solution[From];
While temp<>NIL do （搜索主體）
Begin
a:=nUsed[temp^.Split];
If not a then inc(cost);
nUsed[temp^.Split]:=True;
b:=nUsed[From - temp^.Split];
If not b then inc(cost);
nUsed[From-temp^.Split]:=True;
i:=From-1;
While (i>1) and (not nUsed) do dec(i);
GetCost(i,Cost);
If not a then dec(cost);
If not b then dec(cost);
nUsed[From-temp^.Split]:=b;
nUsed[temp^.Split]:=a;
temp:=temp^.next;
End;
End;
Begin
For i:=2 to Max do（動態規劃計算所有解）
Begin
count:=0;
min:=32767;
For j:=1 to i div 2 do （將I分解為I-J和J）
Begin
c:=32767;
FillChar(nUsed,Sizeof(nUsed),0);
nUsed[j]:=True;nUsed[i-j]:=True;
If j=i-j then GetCost(i-j,1)
Else GetCost(i-j,2);
If c<min then
Begin
count:=1;
min:=c;
plan[count]:=j;
End
Else if c=min then
Begin
inc(count);
plan[count]:=j;
End;
End;
new(solution); （構造解答鏈表）
solution^.split:=plan[1];
solution^.next:=NIL;
Cost:=min;
tail:=solution;
For j:=2 to count do
Begin
new(temp);
temp^.split:=plan[j];
temp^.next:=NIL;
tail^.next:=temp;
tail:=temp;
End;
End;
End;
背包問題：
一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,
每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max{f(x-i)+c[i]} 當x>=w[i] 1<=i<=n
可使用遞歸法解決問題程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,編程很簡單,但當m較大時,容易超時.
4.2 改進的遞歸法
改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函數的值保存起來,開辟一個
一維數組即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.

H. 背包問題的演算法

3.2 背包問題
背包問題有三種

1.部分背包問題

一個旅行者有一個最多能用m公斤的背包，現在有n種物品，它們的總重量分別是W1，W2，...,Wn,它們的總價值分別為C1,C2,...,Cn.求旅行者能獲得最大總價值。

解決問題的方法是貪心演算法:將C1/W1,C2/W2,...Cn/Wn,從大到小排序,不停地選擇價值與重量比最大的放人背包直到放滿為止.

2.0/1背包

一個旅行者有一個最多能用m公斤的背包，現在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價值分別為C1,C2,...,Cn.若每種物品只有一件求旅行者能獲得最大總價值。

<1>分析說明:

顯然這個題可用深度優先方法對每件物品進行枚舉(選或不選用0,1控制).

程序簡單,但是當n的值很大的時候不能滿足時間要求，時間復雜度為O（2n）。按遞歸的思想我們可以把問題分解為子問題,使用遞歸函數

設 f(i，x)表示前i件物品，總重量不超過x的最優價值

則 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））

f（n，m）即為最優解，邊界條件為f（0，x）＝0 ，f(i,0)=0;

動態規劃方法(順推法)程序如下:

程序如下：

program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;

for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.

使用二維數組存儲各子問題時方便，但當maxm較大時如maxn=2000時不能定義二維數組f,怎麼辦,其實可以用一維數組,但是上述中j:=1 to m 要改為j:=m downto 1,為什麼?請大家自己解決。

3.完全背包問題

一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,

每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.

求旅行者能獲得的最大總價值。

本問題的數學模型如下：

設 f(x)表示重量不超過x公斤的最大價值，

則 f(x）=max{f(x-w[i])+c[i]} 當x>=w[i] 1<=i<=n

程序如下:（順推法）

program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
f(0):=0;
for i:=1 to m do
for j:=1 to n do
begin
if i>=w[j] then t:=f[i-w[j]]+c[j];
if t>f[i] then f[i]:=t
end;
writeln(f[m]);
end.

I. C語言貪心演算法 背包問題

if(k!=i)
t=T[i];
T[i]=T[k];
T[k]=t;
交換操作的三步要用{}括起來,不然只有t=T[i];是if的執行語句

J. 計算機演算法分析考試：動態規劃0-1背包問題，怎麼算

問題描述：
給定n種物品和一背包，物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品（物品不能分割），使得裝入背包中物品的總價值最大?

抽象描述如下：
x[n]:表示物品的選擇，x[i]=1表示選擇放進物品i到背包中。