文章目錄

• • 1. 問題引入
  • 2. 動(dòng)態(tài)規(guī)劃求解0-1背包
  • 3. 復(fù)雜度
  • 4. 0-1背包升級(jí)版（帶價(jià)值）
  • 5. 0-1背包升級(jí)版（帶價(jià)值）DP解法

1. 問題引入

前面講了0-1背包的回溯解決方法，它是窮舉所有可能，復(fù)雜度是指數(shù)級(jí)別的，如何降低時(shí)間復(fù)雜度呢？

對(duì)于一組不同重量、不可分割的物品，我們需要選擇一些裝入背包，在滿足背包最大重量限制的前提下，背包中物品總重量的最大值是多少呢？

假設(shè)背包的最大承載重量是9。有5個(gè)不同的物品，重量分別是2，2，4，6，3。把回溯求解過程，用遞歸樹畫出來，就是下面這個(gè)樣子：

從上面圖中可以看出有些函數(shù)被重復(fù)計(jì)算（之前遞歸中也講到了），我們希望當(dāng)計(jì)算到已經(jīng)計(jì)算過的函數(shù)時(shí)，不要重復(fù)計(jì)算，直接拿來用，避免重復(fù)勞動(dòng)。

還是前面的0-1背包問題，分別添加和不添加重復(fù)計(jì)算判斷語句，查看效果

#include <iostream> #define MaxWeight 9 //背包承載極限 using namespace std; bool mem [5][9]; int counttimes; void fill(int i, int curWeight, int *bag, int N, int &maxweightinbag) {cout << "調(diào)用次數(shù): " << ++counttimes << endl;if(curWeight == MaxWeight || i == N)//到達(dá)極限了，或者考察完所有物品了{if(curWeight > maxweightinbag)maxweightinbag = curWeight;//記錄歷史最大裝載量return;}//-----注釋掉以下3行查看效果-------if(mem[i][curWeight])return;mem[i][curWeight] = true;//---------------------------------fill(i+1,curWeight,bag,N,maxweightinbag);//不選擇當(dāng)前i物品，cw不更新if(curWeight+bag[i] <= MaxWeight)//選擇當(dāng)前i物品，cw更新{//沒有達(dá)到極限，繼續(xù)裝fill(i+1,curWeight+bag[i],bag,N,maxweightinbag);} } int main() {const int N = 5;int bag[N] = {2,2,4,6,3};int maxweightinbag = 0;fill(0,0,bag,N,maxweightinbag);cout << "最大可裝進(jìn)背包的重量是：" << maxweightinbag;return 0; }

2. 動(dòng)態(tài)規(guī)劃求解0-1背包

• 把整個(gè)求解過程分為n個(gè)階段，每個(gè)階段會(huì)決策一個(gè)物品是否放到背包中。每個(gè)物品決策（放入或者不放入背包）完之后，背包中的物品的重量會(huì)有多種情況，也就是說，背包會(huì)達(dá)到多種不同的狀態(tài)，對(duì)應(yīng)到遞歸樹中，就是有很多不同的節(jié)點(diǎn)。
• 把每一層重復(fù)的狀態(tài)（節(jié)點(diǎn)）合并，只記錄不同的狀態(tài)，然后基于上一層的狀態(tài)集合，來推導(dǎo)下一層的狀態(tài)集合。我們可以通過合并每一層重復(fù)的狀態(tài)，這樣就保證每一層不同狀態(tài)的個(gè)數(shù)都不會(huì)超過MaxWeight個(gè)（MaxWeight表示背包的承載極限）。于是，我們就成功避免了每層狀態(tài)個(gè)數(shù)的指數(shù)級(jí)增長(zhǎng)。
• 用一個(gè)二維數(shù)組states[N][MaxWeight+1], 來記錄每層可以達(dá)到的不同狀態(tài)

bag[N] = {2,2,4,6,3}; MaxWeight = 9

• 第0個(gè)（下標(biāo)從0開始編號(hào)）物品的重量是2，要么裝，要么不裝，決策完之后，會(huì)對(duì)應(yīng)背包的兩種狀態(tài)，背包中物品的總重量是0或者2。我們用states[0][0]=true和states[0][2]=true 來表示這兩種狀態(tài)。
  
• 第1個(gè)物品的重量也是2，基于之前的背包狀態(tài)，在這個(gè)物品決策完之后，不同的狀態(tài)有3個(gè)，背包中物品總重量分別是0（0+0），2（0+2 or 2+0），4（2+2）。我們用states[1][0]=true，states[1][2]=true，states[1][4]=true來表示這三種狀態(tài)。
  
• 只需要在最后一層，找一個(gè)值為true的最接近 MaxWeight（這里是9）的值，就是背包中物品總重量的最大值。

/*** @description: 0-1背包--dp應(yīng)用* @author: michael ming* @date: 2019/7/9 1:13* @modified by: */ #include <iostream> #define MaxWeight 9 //背包承載極限 const int N = 5; //背包個(gè)數(shù) using namespace std; bool states[N][MaxWeight+1];//全局參數(shù)自動(dòng)初始化，默認(rèn)是false int fill_dp(int *bag, int N) {states[0][0] = true;//第1個(gè)背包不放if(bag[0] <= MaxWeight)states[0][bag[0]] = true;//第1個(gè)背包放for(int i = 1; i < N; ++i)//動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移{for(int j = 0; j <= MaxWeight; ++j)//不把第i個(gè)物品放入背包{if(states[i-1][j] == true)states[i][j] = states[i-1][j];//把上一行的狀態(tài)復(fù)制下來（i不放物品）}for(int j = 0; j+bag[i] <= MaxWeight; ++j)if(states[i-1][j] == true)states[i][j+bag[i]] = true;//把第i個(gè)物品放入背包}for(int i = MaxWeight; i >= 0; --i)//把最后一行，從后往前找最重的背包{if(states[N-1][i] == true)return i;//最大重量}return 0; } int main() {int bag[N] = {2,2,4,6,3};cout << "最大可裝進(jìn)背包的重量是：" << fill_dp(bag,N);return 0; }

3. 復(fù)雜度

上面就是一種用動(dòng)態(tài)規(guī)劃解決問題的思路。把問題分解為多個(gè)階段，每個(gè)階段對(duì)應(yīng)一個(gè)決策。記錄每一個(gè)階段可達(dá)的狀態(tài)集合（去掉重復(fù)的），然后通過當(dāng)前的狀態(tài)集合，來推導(dǎo)下一階段的狀態(tài)集合，動(dòng)態(tài)地往前推進(jìn)。

• 用回溯算法解決這個(gè)問題的時(shí)間復(fù)雜度O（2ⁿ），是指數(shù)級(jí)的。

• 上面DP代碼耗時(shí)最多的部分是代碼中的兩層for循環(huán)，所以時(shí)間復(fù)雜度是O（N * MaxWeight）。N表示物品個(gè)數(shù)，MaxWeight表示背包承載極限。

• 盡管動(dòng)態(tài)規(guī)劃的執(zhí)行效率比較高，但是就上面DP代碼實(shí)現(xiàn)來說，我們需要額外申請(qǐng)一個(gè)N*（MaxWeight+1）的二維數(shù)組，對(duì)空間的消耗比較多。所以，動(dòng)態(tài)規(guī)劃是一種空間換時(shí)間的解決思路。有什么辦法可以降低空間消耗嗎？

• 實(shí)際上，我們只需要一個(gè)大小為 MaxWeight+1 的一維數(shù)組就可以解決這個(gè)問題。動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移的過程，都可以基于這個(gè)一維數(shù)組來操作。具體的代碼如下。

/*** @description: * @author: michael ming* @date: 2019/7/15 22:00* @modified by: */ #include <iostream> #define MaxWeight 9 //背包承載極限 const int N = 5; //背包個(gè)數(shù) using namespace std; bool states[MaxWeight+1];//全局參數(shù)自動(dòng)初始化，默認(rèn)是false int fill_dp(int *bag, int N) {states[0] = true;//第1個(gè)背包不放if(bag[0] <= MaxWeight)states[bag[0]] = true;//第1個(gè)背包放for(int i = 1; i < N; ++i)//動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移{for(int j = MaxWeight-bag[i]; j >= 0; --j)//把第i個(gè)物品放入背包{if(states[j] == true)states[j+bag[i]] = true;}}for(int i = MaxWeight; i >= 0; --i)//輸出結(jié)果{if(states[i] == true)return i;//最大重量}return 0; } int main() {int bag[N] = {2,2,4,6,3};cout << "最大可裝進(jìn)背包的重量是：" << fill_dp(bag,N);return 0; }

內(nèi)層for循環(huán)，j 需要從大到小處理，如果從小到大，會(huì)出現(xiàn)重復(fù)計(jì)算

4. 0-1背包升級(jí)版（帶價(jià)值）

每個(gè)物品對(duì)應(yīng)著一種價(jià)值，不超過背包載重極限，求可裝入背包的最大總價(jià)值。

//--------回溯解法------------------- int maxV = -1; // 最大價(jià)值放到 maxV 中 int weight[5] = {2,2,4,6,3}; // 物品的重量 int value[5] = {3,4,8,9,6}; // 物品的價(jià)值 int N = 5; // 物品個(gè)數(shù) int MaxWeight = 9; // 背包承受的最大重量 void f(int i, int cw, int cv) { // 調(diào)用 f(0, 0, 0)if (cw == MaxWeight || i == N) { // cw==MaxWeight 表示裝滿了，i==N 表示物品都考察完了if (cv > maxV) maxV = cv;return;}f(i+1, cw, cv); // 選擇不裝第 i 個(gè)物品if (cw + weight[i] <= w) {f(i+1, cw+weight[i], cv+value[i]); // 選擇裝第 i 個(gè)物品} }

對(duì)上面代碼畫出遞歸樹，每個(gè)節(jié)點(diǎn)表示一個(gè)狀態(tài)。現(xiàn)在我們需要3個(gè)變量（i，cw，cv）來表示一個(gè)狀態(tài)。其中，i表示即將要決策第i個(gè)物品是否裝入背包，cw表示當(dāng)前背包中物品的總重量，cv表示當(dāng)前背包中物品的總價(jià)值。

• 我們發(fā)現(xiàn)，在遞歸樹有幾個(gè)節(jié)點(diǎn)的 i 和 cw 是完全相同的，比如（2，2，4）和（2，2，3）。
• 在背包中物品總重量一樣的情況下，f（2，2，4）這種狀態(tài)的物品總價(jià)值更大，可以舍棄 f（2，2，3）這種狀態(tài)，只需要沿著 f（2，2，4）這條決策路線繼續(xù)往下決策就可以。
• 也就是，對(duì)于（i，cw）相同的不同狀態(tài)，只需要保留 cv 值最大的那個(gè)，繼續(xù)遞歸處理，其他狀態(tài)不予考慮。

5. 0-1背包升級(jí)版（帶價(jià)值）DP解法

• 把整個(gè)求解過程分為n個(gè)階段，每個(gè)階段會(huì)決策一個(gè)物品是否放到背包中。
• 每個(gè)階段決策完之后，背包中的物品的總重量以及總價(jià)值，會(huì)有多種情況。
• 用一個(gè)二維數(shù)組 states[N][MaxWeight+1]，來記錄每層可以達(dá)到的不同狀態(tài)。
• 這里數(shù)組存儲(chǔ)的值不再是bool類型的了，而是當(dāng)前狀態(tài)對(duì)應(yīng)的最大總價(jià)值。
• 把每一層中（i，cw）重復(fù)的狀態(tài)（節(jié)點(diǎn)）合并，只記錄cv值最大的那個(gè)狀態(tài)，然后基于這些狀態(tài)來推導(dǎo)下一層的狀態(tài)。

/*** @description: 0-1背包帶價(jià)值，dp解法* @author: michael ming* @date: 2019/7/16 0:07* @modified by: */ #include <iostream> #define MaxWeight 9 //背包承載極限 const int N = 5; //背包個(gè)數(shù) using namespace std; int fill_value_dp(int* weight, int* value, int N) {int (*states) [MaxWeight+1] = new int [N][MaxWeight+1];for (int i = 0; i < N; ++i) // 初始化 states{for (int j = 0; j < MaxWeight+1; ++j)states[i][j] = -1;}states[0][0] = 0;//第一個(gè)不放，價(jià)值0存入statesif (weight[0] <= MaxWeight){states[0][weight[0]] = value[0];//第一個(gè)放入背包}for (int i = 1; i < N; ++i) // 動(dòng)態(tài)規(guī)劃，狀態(tài)轉(zhuǎn)移{for (int j = 0; j <= MaxWeight; ++j){ // 不選擇第 i 個(gè)物品if (states[i-1][j] >= 0)states[i][j] = states[i-1][j];//直接復(fù)制上一層的狀態(tài)}for (int j = 0; j+weight[i] <= MaxWeight; ++j){ // 選擇第 i 個(gè)物品if (states[i-1][j] >= 0){int v = states[i-1][j] + value[i];if (v > states[i][j+weight[i]]){//只存價(jià)值最大的states[i][j+weight[i]] = v;}}}}// 找出最大值int maxvalue = -1;// 最大價(jià)值放到 maxvalue 中for (int j = 0; j <= MaxWeight; ++j){if (states[N-1][j] > maxvalue)maxvalue = states[N-1][j];}delete [] states;return maxvalue; } int main() {int weight[5] = {2,2,4,6,3}; // 物品的重量int value[5] = {3,4,8,9,6}; // 物品的價(jià)值cout << "最大可裝進(jìn)背包的價(jià)值是：" << fill_value_dp(weight,value,N);return 0; }

時(shí)間和空間復(fù)雜度都是O(N * MaxWeight)


使用一維數(shù)組也可DP解題，空間復(fù)雜度減小為O（MaxWeight）

/*** @description: 0-1背包帶價(jià)值，dp解法(狀態(tài)存儲(chǔ)用一維數(shù)組)* @author: michael ming* @date: 2019/7/16 22:17* @modified by: */ #include <iostream> #define MaxWeight 9 //背包承載極限 const int N = 5; //背包個(gè)數(shù) using namespace std; int fill_value_dp(int* weight, int* value, int N) {int *states = new int [MaxWeight+1];for (int i = 0; i < MaxWeight+1; ++i) // 初始化 states{states[i] = -1;}states[0] = 0;//第一個(gè)不放，價(jià)值0存入statesif (weight[0] <= MaxWeight){states[weight[0]] = value[0];//第一個(gè)放入背包}for (int i = 1; i < N; ++i) // 動(dòng)態(tài)規(guī)劃，狀態(tài)轉(zhuǎn)移{for (int j = MaxWeight-weight[i]; j >= 0; --j) // for (int j = 0; j <= MaxWeight-weight[i]; ++j){ // 選擇第 i 個(gè)物品if (states[j] >= 0){int v = states[j] + value[i];if (v > states[j+weight[i]]){//只存價(jià)值最大的states[j+weight[i]] = v;}}}}// 找出最大值int maxvalue = -1;// 最大價(jià)值放到 maxvalue 中for (int i = 0; i <= MaxWeight; ++i){if (states[i] > maxvalue)maxvalue = states[i];}delete [] states;return maxvalue; } int main() {int weight[N] = {2,2,4,6,3}; // 物品的重量int value[N] = {3,4,8,9,6}; // 物品的價(jià)值cout << "最大可裝進(jìn)背包的價(jià)值是：" << fill_value_dp(weight,value,N);return 0; }

最大可裝進(jìn)背包的價(jià)值是：18
一維數(shù)組變化過程如下：

總結(jié)

以上是生活随笔為你收集整理的动态规划算法（Dynamic Programming）之0-1背包问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。