1、在動態(tài)規(guī)劃中，參與競賽的學生應該從競爭關(guān)系和獨立關(guān)系(你做你的，我做我的，程序和算法保密，彼此欣賞對方的失敗和自己的成功)轉(zhuǎn)變?yōu)楹献鲗W習關(guān)系(學習任務(wù)通過相互合作完成，如算法討論，集中編程和相互數(shù)據(jù)測量)，2。斐波那契數(shù)列F(n)，3。遞歸與動態(tài)規(guī)劃。遞歸版本：f (n) 1如果n=0或n=1則2返回1 3否則4返回f (n-1) f (n-2)，動態(tài)編程：f (n) 1 a 0=a 1 1 2對于I 2到n做3 a ，有效！算法復雜度為O(n)，4，并對該方法進行了總結(jié)。構(gòu)造了一個公式，表明問題的解是與其子問題的解相關(guān)的公式。例如，F(xiàn)(n)=F(n-1) F(n-2)。將這些子問題編入索引，

2、以便在表中更好地存儲和檢索(即，首先，填寫最小子問題的解。這確保了當我們解決一個特殊的子問題時，我們可以使用比它小的所有可用子問題的解。出于歷史原因，我們稱這種方法為：動態(tài)編程。在20世紀40年代后期(計算機很少普及)，這些規(guī)劃設(shè)計與“列表”方法有關(guān)。5.動態(tài)規(guī)劃算法，將待解決的問題分解成若干個數(shù)字。動態(tài)規(guī)劃算法通常用于解決具有某些最優(yōu)性質(zhì)的問題。動態(tài)規(guī)劃算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題。最優(yōu)子結(jié)構(gòu)的性質(zhì)：一個問題的最優(yōu)解包含其子問題的最優(yōu)解。也就是說，不管先前的策略如何，隨后的決策必須是基于當前狀態(tài)的最優(yōu)決策(由先前的決策生成)。重疊子問題：用遞歸算法自上而下解決問題時，每次生成的

3、子問題并不總是新的，有些問題會重復計算。每個子問題只解決一次，然后保存解決方案。當你將來遇到同樣的問題時，你可以直接引用它，而不必再次解決它。原則7。動態(tài)規(guī)劃，解決問題的基本特征，1。動態(tài)規(guī)劃一般解決最大值問題(最優(yōu)、最大、最小、最長)；通過動態(tài)規(guī)劃解決的問題通常是離散的，并且可以分解(分成階段)；3.動態(tài)規(guī)劃所解決的問題必須包括最優(yōu)子結(jié)構(gòu)，即N的最優(yōu)性可以由(N-1)的最優(yōu)性導出。8.動態(tài)規(guī)劃算法有四個步驟：1 .描述最優(yōu)解的結(jié)構(gòu)特征。(一維、二維、三維陣列)2。遞歸定義最優(yōu)解。(狀態(tài)轉(zhuǎn)移方程)3。用自下而上的方法計算最優(yōu)解解決問題的基本步驟，原理，9，示例，示例1。斐波納契數(shù)列F(n)，第

4、一步：用F(n)來表示斐波納契數(shù)列中第n個數(shù)的值；第二步：狀態(tài)轉(zhuǎn)移方程；步驟3:用自下而上的方法計算最優(yōu)解；步驟4:分析并構(gòu)建數(shù)組中問題的解決方案；10，實施例2。輸入n并找到n！步驟1:用F(n)表示n！的價值；步驟2:狀態(tài)轉(zhuǎn)移方程；第三步：用自下而上的方法計算最優(yōu)解；例11；例3:排隊買票；一場音樂會即將舉行。目前，N個粉絲排隊購票，一人買一張票，而售票處規(guī)定一人最多只能買兩張票。假設(shè)第I個球迷購買一張票需要時間t1(1In)，并且球隊中的兩個相鄰球迷(第j和第j)也可以通過其中一個球迷購買兩張票，而另一個球迷不需要排隊，那么這兩個球迷購買兩張票的時間變成了Rj，如果rj f I-1 t

5、I那么7fI問題描述有一個正整數(shù)序列：b1，b2，bn，下標i1TK(1=i=K)。你的任務(wù)是知道所有N個學生的身高，并計算出至少有幾個學生需要排隊，這樣其余的學生就可以組成一個合唱隊。輸入的第一行是一個整數(shù)N(2=N=100)，表示學生總數(shù)。第一行有n個用空格分隔的整數(shù)，第I個整數(shù)Ti(130=Ti w然后6 Pi，w Pi-1，w；7否則8 p I，w max p I-1，w，p I-1，w-wi vi，運行時間： (NW)，38，0-1，背包問題的動態(tài)規(guī)劃，0:n，1，w P(i-1，w)，拿走物品I，不要拿走物品I，I，w，39，P(i，w)=max VI p (I-1，w-wi)，P

6、(i-1) 12，22，22，10，12，12 W)首先，當物品1向左移動時被取走，當物品1直線移動時不被取走，41，子問題的重復，0:n，1，W，I-1，0，p (I，w)=最大值VI P(i-1，w-wi)，p (I-wi) W)，子問題的重復，1，0，0，0，1，0，1，1 示例：n=5，p=6，3，5，4，6，w=2，2，6，5，4，w=10，43，擴展1:包裝問題(vijos 1133)，有一個容量為v(正整數(shù))的箱子，要求將多達1，000個物品從N個物品中放入箱子，以最小化箱子的剩余空間。輸入格式輸入格式，第一行，一個整數(shù)，表示盒子的容量；第二行是一個整數(shù)，表示有n個項目；以下n行

7、分別代表這n個項目各自的體積。Output Format outputformat，一個整數(shù)，指示框的剩余空間。樣本輸入，24 6 8 3 12 7 9 7，樣本輸出，0，44，擴展2:藥草采集(vijos1104)。陳晨是一個天才和聰明的孩子，他的夢想是成為世界上最偉大的醫(yī)生。為此，他想崇拜附近最有聲望的醫(yī)生。為了判斷他的資格，醫(yī)生給他出了一道難題。醫(yī)生帶他到一個滿是草藥的山洞，對他說：“孩子，這個山洞里有一些不同的草藥。采摘每一株植物都需要一些時間，每一株植物都有自己的價值。我會給你一些時間，在此期間你可以采摘一些草藥。如果你是一個聰明的孩子，你應該能夠最大限度地提高草藥的總價值。”如果你

8、是陳晨，你能完成這項任務(wù)嗎？輸入格式，第一行輸入有兩個整數(shù)T(1=T=1000)和M(1=M=100)，用空格隔開，T代表采集草藥的總時間，M代表洞穴中草藥的數(shù)量。以下m行各包含兩個介于1和100(包括1和100)之間的整數(shù)，表示采摘某種草藥的時間和該草藥的價值。輸出格式，輸出包括一行，僅包含一個整數(shù)，表示在指定時間內(nèi)可以收集的草藥的最大總值。樣本輸入，70 3 71 100 69 1 1 2，樣本輸出，3，45，擴展3:快樂的金明(vijos 1317)，金明今天很開心，他家新買的房子需要鑰匙，新房子里有一個寬敞的房間給自己。令他高興的是，我媽媽昨天對他說，“你有最終的決定權(quán)，你需要買什么，

9、如何裝飾你的房間，只要不超過人民幣?！?。金明今天一大早就開始做預算，但是他想買太多的東西，這肯定會超過他媽媽的N元限額。因此，他為每個項目指定了一個重要度，分為五個等級：整數(shù)15表示第五級是最重要的。他還從網(wǎng)上找到了每件商品的價格(它是一個整數(shù))。他希望每個產(chǎn)品的價格和重要性的總和不超過N元(可以等于N元)。假設(shè)第j個項目的價格為vj，重要性為wj，則選擇總共K個項目，序列號為j1.jk，總和為vj1*wj1.vjk*wjk。請幫助金m(25)設(shè)計一個符合要求的購物清單，并輸入格式輸入格式。從第2行到第m 1行，編號為j-1的項目的基本數(shù)據(jù)在第j行給出，每一行有兩個非負整數(shù)v p(其中v代表項

10、目的價格(v10000)，p代表項目的重要性(15)，46，輸出格式輸出格式，輸出只有一個正整數(shù)。對于價格和不超過總金額的項目的重要性的乘積的最大值(100，000，000)，樣本輸入是樣本輸入，1000 5 800 2 400 5 300 5 400 3 200 2，樣本輸出是樣本輸出，3900，47，擴展4:金明的預算計劃(vijos 1313)。金明今天很開心，在家里買的。令他高興的是，我媽媽昨天對他說，“你有最終的決定權(quán)，你需要買什么，如何裝飾你的房間，只要不超過人民幣。”。今天一早，金明開始做預算。他把他想買的東西分成兩類：主要零件和配件。附件從屬于某個主要部分。下表是主要零件和附件

11、的一些示例：主要零件和附件的計算機打印機、掃描儀書架和文具椅子中書籍的臺燈。如果你想購買被歸類為配件的物品，你必須首先購買配件所屬的主要部件。每個主要零件可以有0個、1個或2個附件。附件不再有自己的附件。金明想買很多東西，這肯定會超過她媽媽限定的N元。因此，他為每個項目指定了一個重要度，分為五個等級：整數(shù)15表示第五級是最重要的。他還在網(wǎng)上找到了每件商品的價格(10元的整數(shù)倍)。他希望每個產(chǎn)品的價格和重要性的總和不超過N元(可以等于N元)。假設(shè)Jth項目的價格為vj，重要性為wj，則總共選擇K個項目，編號為j1，j2，依次為jk，和為V J1 * W J1 V J2 * W J2.請幫助金明設(shè)計一份符合要求的購物清單。48，輸入格式輸入格式，輸入文件的第一行是由空格分隔的兩個正整數(shù)：N m其中N(0，表示該項目是一個附件，q是主要部分的數(shù)字)，輸出格式輸出格式，輸出