動(dòng)態(tài)規(guī)劃1—-背包問(wèn)題
大家好，這次給大家分享的題會(huì)比以往難一點(diǎn)咱揍，學(xué)會(huì)了這道題的解題思想并思，對(duì)動(dòng)態(tài)規(guī)劃的掌握就更上一層樓了- 下面先給大家講有關(guān)于動(dòng)態(tài)規(guī)劃的兩個(gè)概念（其實(shí)在上兩次的題中我們一直有在用）
- 最優(yōu)子結(jié)構(gòu)
對(duì)于一個(gè)問(wèn)題键袱，我們可以拆分成很多相似的子問(wèn)題勾习，并且要算出原問(wèn)題的最優(yōu)解之前含衔，
必須先算出子問(wèn)題的最優(yōu)解族奢。例如跳臺(tái)階的那道題氮兵，f(n-1),f(n-2)…這些就是子問(wèn)題
，我們要算出f(n)之前歹鱼，就必須先算出f(n-1),f(n-2)泣栈。 - 狀態(tài)
所謂的狀態(tài)就是指這個(gè)問(wèn)題解決了沒(méi)有（包括子問(wèn)題）。我們用1表示已解決弥姻，用0表示
未解決（這個(gè)用什么數(shù)字表示都行）南片。例如當(dāng)我們求出了f(n-1)時(shí)，就把它的狀態(tài)記錄
為1庭敦，否則記錄為0疼进。記錄狀態(tài)主要是為了防止大量的重復(fù)求解
問(wèn)題：
給定n種物品和一背包。物品i的重量是wi秧廉，其價(jià)值為vi伞广，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品疼电，使得裝
入背包中物品的總價(jià)值最大?
????個(gè)人感覺(jué)這道經(jīng)典的0-1背包問(wèn)題還是挺難的嚼锄，
????反正當(dāng)時(shí)看了好幾遍才看懂，才理解它的做法
解析：
當(dāng)然蔽豺，對(duì)于這道題区丑，如果你想要暴力遞歸的方法做也是可以的。例如我們可以把所有
物品看出一個(gè)集合，然后把所有子集都求出來(lái)沧侥，然后看看那個(gè)集合的物品裝的下且價(jià)值
最高可霎。不過(guò)時(shí)間復(fù)雜度是2的n次方。指數(shù)增長(zhǎng)的復(fù)雜度自己掂量宴杀。
-
暴力遞歸的做法如下(C++)（我就不帶大家找遞歸結(jié)束等條件了）
int n, C;//n表示物品的數(shù)量癣朗，C表示背包能承載的重量 int v[Max_n+1], w[Max_n+1];//v[i]表示地i個(gè)物品的價(jià)值，w[i]表重量 //從第i個(gè)物品挑選總重量小于j的部分 //**下標(biāo)從1開(kāi)始** int solve(int i, int j){ int sum; if(i > n){//已經(jīng)沒(méi)有物品了（因?yàn)橄聵?biāo)從0開(kāi)始的） sum = 0; }else if(j < w[i]){ //這個(gè)物品裝不下 sum = solve(i+1, j);//挑選下一個(gè)物品 }else{ //物品裝的下 //分是否挑選物品兩種情況 //不裝旺罢，則嘗試挑選 下一個(gè) //裝的話旷余，背包容量變?yōu)閖-w[i],單價(jià)值多了v[i] sum = max(solve(i+1, j), solve(i+1, j-w[i])+v[i]); return sum; } } int main(){ solve(n, C); } - 重復(fù)算了同一個(gè)函數(shù)很多遍，如同
- 數(shù)據(jù)變量說(shuō)明：
- 對(duì)于一種物品主经，要么裝入背包荣暮，要么不裝庭惜。所以對(duì)于一種物品的裝入狀態(tài)可以取0和1.我們?cè)O(shè)物品i的裝入狀態(tài)為xi,xi∈ (0,1)罩驻。
- 數(shù)據(jù)：物品個(gè)數(shù)n=5,物品重量w[n]={0，2护赊，2惠遏，6，5骏啰，4},物品價(jià)值V[n]={0节吮，6，3判耕，5透绩，4，6},C=10壁熄，（為了方便說(shuō)明帚豪，小標(biāo)從1開(kāi)始）
- 對(duì)于m(i,j)就表示可選物品為i…n背包容量為j(總重量)時(shí)背包中所放物品的最大價(jià)值。
- 建立如下方格圖（其實(shí)就是一個(gè)二維數(shù)組）
{?
? ? //采用從底到頂?shù)捻樞騺?lái)設(shè)置m[i][j]的值?
? ? //首先放w[n]?
? ? for(int j = 0; j <= c; j++){
? ? ? if(j < w[n]) m[n][j] = 0;? ? //j小于w[n],放不下草丧，把所對(duì)應(yīng)的值設(shè)為0狸臣，否則就為可以放置?
? ? ? else? ? ? ? m[n][j] = v[n];?
}
?//對(duì)剩下的n-1個(gè)物品進(jìn)行放置。?
? ? int i;?
? ? for(i = n-1; i >= 1; i--){
? ? ? ? for(int j = 0; j <= c; j++)?
? ? ? ? ? if(j < w[i]) {?
? ? ? ? ? ? ? ? ? m[i][j] = m[i+1][j];//如果j < w[i]則昌执，表示放不下烛亦，它等于上一個(gè)位置的值。
}else {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //否則懂拾，就考慮是否要放置煤禽，原理和遞歸做法相似? ? ? ? ? ? ?
? ? ? ? ? ? ? ? m[i][j] = max(m[i+1][j], m[i+1][j-w[i]] + v[i]);
}
????return a[1][c];//m[1][c]就是所求最大值
}
- 動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)就是，將問(wèn)題化為求解子問(wèn)題岖赋，前一個(gè)子問(wèn)題最值問(wèn)題求解了呜师，如果你找到子問(wèn)題與當(dāng)前問(wèn)題的關(guān)系，那么當(dāng)前問(wèn)題就解決了贾节，是一個(gè)迭代的過(guò)程汁汗。
另外衷畦，將搜索進(jìn)行記憶化，也就是說(shuō)把算過(guò)的記錄起來(lái)知牌。 - 下面給大家推薦一道類(lèi)似的題祈争，做法和這個(gè)背包的幾乎一樣，考考大家角寸，給大家練練手菩混。
問(wèn)題描述：
小明是一個(gè)喜歡看動(dòng)畫(huà)片的人，自從成為ACMer（ACM愛(ài)好者）之后扁藕，他又迷上了網(wǎng)上做題沮峡。做題讓他快樂(lè)，不過(guò)這也是需要付出精力的Ｒ诟獭邢疙！
假設(shè)有n道題，Lian做出第i道題后望薄，他可以獲得的快樂(lè)指數(shù)將增加gethappy[i]疟游，而消耗掉的精力將是losspow[i]。
假設(shè)小明初始的快樂(lè)指數(shù)為1痕支，精力為2000颁虐。可以理解卧须，如果他消耗完了所有的精力那他得到再多的快樂(lè)都沒(méi)有用另绩。
你的任務(wù)就是幫他計(jì)算他所能得到的最多的快樂(lè)指數(shù)，且最后他依然有多余的精力（即至少為1）花嘶。
輸入格式
第一行輸入一個(gè)整數(shù)n笋籽，表示有n個(gè)人。(n<=50)
第二行輸入n個(gè)整數(shù)察绷，表示gethappy[1]到gethappy[n]
第三行輸入n個(gè)整數(shù)干签，表示losspow[1]到losspow[n]。
輸出格式
一個(gè)整數(shù)拆撼，表示小明所能獲得的最大快樂(lè)指數(shù)容劳。
輸入樣例
3
15 23 61
350 1301 1513
輸出樣例
77
—————
- 希望大家能有所收獲
- 下次會(huì)給大家推薦一些數(shù)據(jù)結(jié)構(gòu)與算法的書(shū)（都是自己看過(guò)的，感覺(jué)還不錯(cuò)）闸度。
- 如果大家想要這道題的答案竭贩，可以在公眾號(hào)回復(fù)小明的快樂(lè)獲取。
下面二維碼
