acm中dp問題簡單入門講解

《acm中dp問題簡單入門講解》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、ACM暑期集訓(xùn)報告院系：專業(yè)：年級：學(xué)號：姓名：日期：西南交通大學(xué)31目錄目錄1第1章動態(tài)規(guī)劃（dp）21.1簡介21.2教師內(nèi)容51.3基本dp——背包問題61.4若干經(jīng)典dp及常見優(yōu)化91.5類似題目10參考文獻31附錄1暑期集訓(xùn)心得體會3131動態(tài)規(guī)劃（dp）（標(biāo)題采用2號黑體居中，下空1行）1.1簡介（標(biāo)題采用四號黑體，正文內(nèi)容采用小四號字體，1.5倍行距）在解決問題的時候我們經(jīng)常遇到這種問題：在多種方式的操作下我們?nèi)绾蔚玫揭粋€最優(yōu)的方式讓我們得到滿意的結(jié)果。這時候我們大多人的思想就是貪心。不錯貪心確實是一個不錯的算法，首先他簡單容易想到，我們在操作起來也比較容易?，F(xiàn)在我推薦

2、幾道我們oj上的貪心算法的題：soj1562藥品運輸soj1585Climbingmountain。為了引入動歸算法我先拿藥品運輸這道題簡單說一下貪心算法。示例1：藥品運輸（題目采用小四號TimesNewRoman字體）Description5.12大地震后，某災(zāi)區(qū)急需一批藥品，現(xiàn)在有N種藥品需要運往災(zāi)區(qū)，而我們的運輸能力有限，現(xiàn)在僅有M輛運輸車用來運輸這批藥品，已知不同的藥品對災(zāi)區(qū)具有不同的作用（“作用”用一個整數(shù)表示其大小），不同的藥品需要的運輸力（必要的車輛運載力）不同，而不同的車輛也具有不同的運輸力。同時，我們希望不同的藥品用不同的車輛來運輸（避免發(fā)生混淆）?，F(xiàn)在請你幫忙設(shè)計

3、一方案，來使得運往災(zāi)區(qū)的藥品對災(zāi)區(qū)的作用最大。Input第一行包含一個整數(shù)T，表示需要處理的測試數(shù)據(jù)組數(shù)。每一組第一行包括兩個整數(shù)N,M，分別表示藥品總數(shù)，及車輛總數(shù)。接著第二行包含N個整數(shù)（pi<=10000），分別表示每種藥品的作用。接著第三行包含N個整數(shù)，分別表示每種藥品必須得運載力(wi<=1000)。接著第四行包含M個整數(shù)，表示每輛車的運輸力(c<=1000)；（T<=10;N,M<=1000）Output31輸出包括T行，每行僅一個整數(shù)，表示最大的作用值。SampleInput1111037SampleOutput10在該樣例中一輛車只能運一種藥品，親愛的acmer你會很

4、容易想到只要讓每一輛車運送在它運輸力之下的藥品中價值最大的那個就行了，但是這樣是不是最優(yōu)解呢？答案是：恭喜你答對了。但是我怎么選擇車呢？你肯定很隨意就想到我只要從小到大一個個找就ok了。Soeasy，right？不過是不是我們所有的問題這樣都能很隨意的解決呢？Now，接下來的題目，你會發(fā)現(xiàn)我們的貪心，貪不過去了。。。。。。示例2：硬幣問題（soj1787）Description有N種不同面值的硬幣，每種硬幣都是有限個，給定一個上限錢數(shù)W,問用這些硬幣可組成不超過W的最大價值．Input31輸入有多組測試數(shù)據(jù)。每一組測試數(shù)據(jù)為如下形式：WNn1D1n2D2...nNDNW和N分別表示上

5、限錢數(shù)和有N種不同面值的硬幣，n（i）和D（i）表示面值為D（i）的硬幣數(shù)量為n（i），其中有1<=i<=N.0<=W<=100000,0<=N<=10,0<=n(i)<=1000,1<=D(i)<=1000.Output對于每一組測試數(shù)據(jù)，輸出這些硬幣可組成不超過W的最大價值．SampleInput73534125653350633450030610015017350031010010501010SampleOutput7356300031現(xiàn)在我們試一試如果每一次都取滿足條件的最大面值的硬幣那么得到的答案是不是正確的呢？拿第一組數(shù)據(jù)為例：73534125653350第一次取350剩

6、下385第二次取350剩下35第三次取5剩下30依次再取5五次。最終我們?nèi)〉搅?50*2+5*6=730咦。。。。不對?。咳绻?50+125*3+5*2=735豈不是更多？可是我們每一次都取最優(yōu)解啊，為啥結(jié)果不是最優(yōu)的呢？問題出在第一種取法沒有考慮到空間的最大利用化。下面我們引入了動態(tài)規(guī)劃，又習(xí)慣稱之為dp。嚴(yán)格的說，動態(tài)規(guī)劃程序設(shè)計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。對于我們acmer來說dp是一種思想，一種化繁為簡，化大為小的處理問題的方式。上面的硬幣的題就屬于dp的一種——背包問題。后面我會仔細(xì)講，現(xiàn)在就不多說了。在學(xué)習(xí)dp的時候我的建議是，學(xué)習(xí)如何建立狀

7、態(tài)方程。如何把主要問題化成子問題分布求解直至得到最終結(jié)果。如何用dp的思想來解決最優(yōu)解問題。當(dāng)然我不反對多做題。但是大家要通過做題來學(xué)到一些東西。dp是一種思想，若思想達不到真正遇到一道題你還是沒辦法解決。在處理dp的問題中我們一般想到的解決方法就是用空間換取時間，acm一般對time卡的要比memory要嚴(yán)一般tle要比mle多得多。也就是說我們一般不會爆內(nèi)存，但是時間比較容易超時。因此有時候我們確實需要用空間換取一定的時間。但是真正的dp對于空間也是有