動態(tài)規(guī)劃1—-背包問題
大家好，這次給大家分享的題會比以往難一點，學(xué)會了這道題的解題思想，對動態(tài)規(guī)劃的掌握就更上一層樓了- 下面先給大家講有關(guān)于動態(tài)規(guī)劃的兩個概念（其實在上兩次的題中我們一直有在用）
- 最優(yōu)子結(jié)構(gòu)
對于一個問題，我們可以拆分成很多相似的子問題，并且要算出原問題的最優(yōu)解之前，
必須先算出子問題的最優(yōu)解。例如跳臺階的那道題，f(n-1),f(n-2)…這些就是子問題
，我們要算出f(n)之前，就必須先算出f(n-1),f(n-2)。 - 狀態(tài)
所謂的狀態(tài)就是指這個問題解決了沒有（包括子問題）。我們用1表示已解決，用0表示
未解決（這個用什么數(shù)字表示都行）。例如當我們求出了f(n-1)時，就把它的狀態(tài)記錄
為1，否則記錄為0。記錄狀態(tài)主要是為了防止大量的重復(fù)求解
問題：
給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝
入背包中物品的總價值最大?
????個人感覺這道經(jīng)典的0-1背包問題還是挺難的，
????反正當時看了好幾遍才看懂，才理解它的做法
解析：
當然，對于這道題，如果你想要暴力遞歸的方法做也是可以的。例如我們可以把所有
物品看出一個集合，然后把所有子集都求出來，然后看看那個集合的物品裝的下且價值
最高。不過時間復(fù)雜度是2的n次方。指數(shù)增長的復(fù)雜度自己掂量。
-
暴力遞歸的做法如下(C++)（我就不帶大家找遞歸結(jié)束等條件了）
int n, C;//n表示物品的數(shù)量，C表示背包能承載的重量 int v[Max_n+1], w[Max_n+1];//v[i]表示地i個物品的價值，w[i]表重量 //從第i個物品挑選總重量小于j的部分 //**下標從1開始** int solve(int i, int j){ int sum; if(i > n){//已經(jīng)沒有物品了（因為下標從0開始的） sum = 0; }else if(j < w[i]){ //這個物品裝不下 sum = solve(i+1, j);//挑選下一個物品 }else{ //物品裝的下 //分是否挑選物品兩種情況 //不裝，則嘗試挑選 下一個 //裝的話，背包容量變?yōu)閖-w[i],單價值多了v[i] sum = max(solve(i+1, j), solve(i+1, j-w[i])+v[i]); return sum; } } int main(){ solve(n, C); } - 重復(fù)算了同一個函數(shù)很多遍，如同
- 數(shù)據(jù)變量說明：
- 對于一種物品，要么裝入背包，要么不裝。所以對于一種物品的裝入狀態(tài)可以取0和1.我們設(shè)物品i的裝入狀態(tài)為xi,xi∈ (0,1)。
- 數(shù)據(jù)：物品個數(shù)n=5,物品重量w[n]={0，2，2，6，5，4},物品價值V[n]={0，6，3，5，4，6},C=10，（為了方便說明，小標從1開始）
- 對于m(i,j)就表示可選物品為i…n背包容量為j(總重量)時背包中所放物品的最大價值。
- 建立如下方格圖（其實就是一個二維數(shù)組）
{?
? ? //采用從底到頂?shù)捻樞騺碓O(shè)置m[i][j]的值?
? ? //首先放w[n]?
? ? for(int j = 0; j <= c; j++){
? ? ? if(j < w[n]) m[n][j] = 0;? ? //j小于w[n],放不下，把所對應(yīng)的值設(shè)為0，否則就為可以放置?
? ? ? else? ? ? ? m[n][j] = v[n];?
}
?//對剩下的n-1個物品進行放置。?
? ? 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]則，表示放不下，它等于上一個位置的值。
}else {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //否則，就考慮是否要放置，原理和遞歸做法相似? ? ? ? ? ? ?
? ? ? ? ? ? ? ? m[i][j] = max(m[i+1][j], m[i+1][j-w[i]] + v[i]);
}
????return a[1][c];//m[1][c]就是所求最大值
}
- 動態(tài)規(guī)劃的實質(zhì)就是，將問題化為求解子問題，前一個子問題最值問題求解了，如果你找到子問題與當前問題的關(guān)系，那么當前問題就解決了，是一個迭代的過程。
另外，將搜索進行記憶化，也就是說把算過的記錄起來。 - 下面給大家推薦一道類似的題，做法和這個背包的幾乎一樣，考考大家，給大家練練手。
問題描述：
小明是一個喜歡看動畫片的人，自從成為ACMer（ACM愛好者）之后，他又迷上了網(wǎng)上做題。做題讓他快樂，不過這也是需要付出精力的?。?br>假設(shè)有n道題，Lian做出第i道題后，他可以獲得的快樂指數(shù)將增加gethappy[i]，而消耗掉的精力將是losspow[i]。
假設(shè)小明初始的快樂指數(shù)為1，精力為2000?？梢岳斫?，如果他消耗完了所有的精力那他得到再多的快樂都沒有用。
你的任務(wù)就是幫他計算他所能得到的最多的快樂指數(shù)，且最后他依然有多余的精力（即至少為1）。
輸入格式
第一行輸入一個整數(shù)n，表示有n個人。(n<=50)
第二行輸入n個整數(shù)，表示gethappy[1]到gethappy[n]
第三行輸入n個整數(shù)，表示losspow[1]到losspow[n]。
輸出格式
一個整數(shù)，表示小明所能獲得的最大快樂指數(shù)。
輸入樣例
3
15 23 61
350 1301 1513
輸出樣例
77
—————
- 希望大家能有所收獲
- 下次會給大家推薦一些數(shù)據(jù)結(jié)構(gòu)與算法的書（都是自己看過的，感覺還不錯）。
- 如果大家想要這道題的答案，可以在公眾號回復(fù)小明的快樂獲取。
下面二維碼
