1.UVA DP 入門專題 2.夜深人靜寫算法（二） - 動(dòng)態(tài)規(guī)劃 3.算法之動(dòng)態(tài)規(guī)劃 4.什么是動(dòng)態(tài)規(guī)劃？動(dòng)態(tài)規(guī)劃的意義是什么？ 5.01背包問題和完全背包問題 6.背包九講
1.01背包練習(xí) 2.完全背包 多重背包練習(xí) 3.UVA的部分題目
有n件商品，每件商品僅有一件，并且每件商品有自己的價(jià)值v和重量w。現(xiàn)在有一個(gè)最大承載重量為m的背包，求解最多能裝下價(jià)值為多少的商品。
dp[j] = max(dp[j],dp[j-w[i]]+v[i])
1).HDOJ.2955 結(jié)合了概率和獨(dú)立事件的知識(shí)。對(duì)于每個(gè)銀行，小偷有搶或者不搶兩種選擇，并且每個(gè)銀行搶不搶，事件發(fā)生時(shí)獨(dú)立的。兩個(gè)獨(dú)立事件共同發(fā)生的概率，為兩個(gè)事件發(fā)生概率的乘積。這是需要注意的。 另外一點(diǎn)就是，在遇到一些概率的問題的時(shí)候，通常需要將其轉(zhuǎn)換成其對(duì)立事件發(fā)生的概率。這樣解決起來較為容易。
2).HDOJ.3466 題面本身就是一個(gè)簡(jiǎn)單的01背包問題但是關(guān)鍵在于本題卻需要排序，原因是會(huì)影響到后續(xù)物品的選擇。簡(jiǎn)單來說，破壞了動(dòng)態(tài)規(guī)劃的無后效性。 對(duì)于每個(gè)商品，尤其能夠買的臨界值qi和其本身的價(jià)格pi，即當(dāng)手中的錢不夠qi的時(shí)候，商人就不考慮把第i件商品賣給你了。 比如有以下商品：
| label | item1 | item 2 |
|---|---|---|
| q | q1 | q2 |
| p | p1 | p2 |
其中 q1 – p1 < q2 – p2 若想把這兩件商品全部購(gòu)買，則至少需要p1+p2的金錢。那么如果我們沒有這么多金錢怎么辦。這就要考慮到dp時(shí)候的狀態(tài)轉(zhuǎn)移了。 在狀態(tài)轉(zhuǎn)移的時(shí)候，item1能從item2轉(zhuǎn)移的狀態(tài)區(qū)間是[min(q1+p2,m),m]，同理，item2能從item1轉(zhuǎn)移的狀態(tài)區(qū)間是[min(q2+p1,m),m]。對(duì)于p1+q2或p2+q1，個(gè)人的理解是，先買了物品1花費(fèi)p1，因?yàn)楝F(xiàn)在要對(duì)物品2進(jìn)行狀態(tài)轉(zhuǎn)移，則需要錢的數(shù)量大于q2才可以，否則無法進(jìn)行狀態(tài)轉(zhuǎn)移，即物品1的狀態(tài)沒有得到利用，因?yàn)槲覀円M可能重復(fù)的利用這個(gè)區(qū)間。（p2+q1同理可得） 故對(duì)于以上2件商品，我們要看p1+q2和p2+q1孰大孰小。再根據(jù)題目數(shù)據(jù)不難看出 p1 + q2 < p2 + q1。 根據(jù)以上的敘述不難得出結(jié)論：要按qi-pi的差值升序排序，然再做01背包。那么疑問也油然而生：為什么平常的做01背包也沒見排序呀？ 這是因?yàn)槠胀ǖ?1背包pi==qi，也就是說只要有足夠的金錢，就能購(gòu)買物品。故不需要排序。所以以后做這種類型的dp要留個(gè)心眼。
3).HDOJ.2546 這題跟上面的那個(gè)題目也有相似之處，由于此題恒定q為5，我們可以采用別的方法來處理。先按照價(jià)格降序/升序排序，然后把價(jià)格最大的那個(gè)留下來(留給那個(gè)剩余的5塊錢，一邊讓剩余金額最小)。然后以總金額-5為背包容量，除去最貴的剩余菜為商品做01背包即可。
4).HDOJ.2639 此題本身依舊是一個(gè)01背包，但是題目要求輸出的是第k最優(yōu)解，平常題目都是直接輸出最優(yōu)解即可。 根據(jù)背包九講，不難想到肯定要增加一維，使得dp變?yōu)槎S數(shù)組，其中第二維用來表示第K最優(yōu)解。其次分別2個(gè)輔助數(shù)組a[],b[]，容量以題目中的K為上限。實(shí)現(xiàn)方法如下： a.在做01背包的時(shí)候，多增加一層循環(huán)，由1->k的循環(huán)，用來儲(chǔ)存第K個(gè)解。將原本的01背包狀態(tài)轉(zhuǎn)移方程中較大的放到a[]中，較小的放到b[]中。 b.其次對(duì)a[],b[]做處理，依次從這2個(gè)數(shù)組中取出較大的那個(gè)，放到dp[i][k].表示第k解。 代碼如下：
for(int i = 1;i<=n;++i){ for(int j =m;j>=w[i];--j){ int l; for( l = 1;l<=k;l++){ a[l] = dp[j-w[i]][l]+v[i]; b[l] = dp[j][l]; } a[l] = b[l] = -1; int x,y,z; x = y= z = 1; while(z<=k && (a[x]!=-1 || b[y]!=-1)){ if(a[x] > b[y]){ dp[j][z] = a[x];x++;} else {dp[j][z] = b[y];y++;} if(dp[j][z] != dp[j][z-1]) z++; } } }1). 不要忘記初始化dp數(shù)組，和其他的輔助數(shù)組。 2). 在求一些最大最小值，或者是否可以構(gòu)成的時(shí)候，經(jīng)常講dp整個(gè)初始化為INF，或者將dp[0]初始化為0或者1，這個(gè)要具體情況具體分析。
有n件商品，每件商品有無數(shù)件，并且每件商品有自己的價(jià)值v和重量w。現(xiàn)在有一個(gè)最大承載重量為m的背包，求解最多能裝下價(jià)值為多少的商品。
dp[j] = max(dp[j],dp[j-w[i]]+v[i])
1).UVA.674 經(jīng)典的硬幣組成問題，問某個(gè)金額的組成方案有多少種，注意當(dāng)數(shù)據(jù)特別大的時(shí)候要開long long數(shù)組。 2).HDOJ.2159 這題是帶個(gè)數(shù)限制的完全背包，那么最先想到的就是增加一維來表示個(gè)數(shù)。
for(int i =1; i<=k; ++i) { for(int j = a[i].ence; j<=m; ++j) for(int l = 1; l<=s;++l) dp[j][l] = max(dp[j][l],dp[j-a[i].ence][l-1] +a[i].exp); }總的感覺完全背包沒有什么難點(diǎn)，基本上就是套狀態(tài)轉(zhuǎn)移方程即可。
有n件商品，第ai件商品有ci件，并且每件商品有自己的價(jià)值v和重量w。現(xiàn)在有一個(gè)最大承載重量為m的背包，求解最多能裝下價(jià)值為多少的商品。
**F[i，v] = max{F[i ? 1, v ? k ? Ci ] + k ? Wi | 0 ≤ k ≤ Mi}**
一般集合二進(jìn)制優(yōu)化和單調(diào)隊(duì)列優(yōu)化，轉(zhuǎn)換為01背包問題
二進(jìn)制優(yōu)化 即用二進(jìn)制來表示有限的狀態(tài)。通俗點(diǎn)講，就是用1,2,4,8,16……這樣的數(shù)來表示任意一個(gè)有限數(shù)字。如3 = 2+1， 7=4+2+1 如果我們把物品的個(gè)數(shù)，拆分成1個(gè)2個(gè)4個(gè)……在一起的物品，那么就是相當(dāng)于對(duì)這樣的物品做出選擇，即做01背包。 這樣就由多重背包，轉(zhuǎn)換成了01背包的問題。 二進(jìn)制優(yōu)化代碼：
for(int i = 0 ;i<6;++i){ for(int j =1; j<=c[i]; j<<=1){ val[cnt] = j*(i+1); num[cnt++] = j; c[i]-=j; } if(c[i]>0){ val[cnt] = c[i] * (i+1); num[cnt++] = c[i]; } }一般大部分題目都是使用二進(jìn)制優(yōu)化轉(zhuǎn)換成01背包問題，或者是使用單調(diào)隊(duì)列優(yōu)化，極大提高程序效率。
給出2個(gè)字符串，求出這兩個(gè)字符串的最長(zhǎng)公共子序列的長(zhǎng)度。
if(c1[i] == c2[j]) dp[i][j] =dp[i-1][j-1]+1; else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
給出一個(gè)序列，求出他的最長(zhǎng)上升子序列的長(zhǎng)度。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
