文章目錄
-
- 1 背包問題定義
- 2 回溯法
-
- 2.1 回溯法的設計思想
- 2.2 回溯法求解0/1背包問題
- 2.3 算法步驟
- 2.4 代碼實作
- 2.5 實驗結果
-
- 2.5.1 回溯法求解背包問題的搜尋樹
- 2.5.2 搜尋樹生成過程
- 2.5.3實際輸出：
- 2.6 回溯算法的效率分析
- 3 貪婪算法
-
- 3.1 貪婪法的設計思想
- 3.2 貪婪法解決部分背包問題
-
- 3.2.1 算法設計：
- 3.2.2 實驗結果
- 3.3貪婪算法解決0/1背包問題
-
- 3.3.1 算法設計
- 3.3.2 實驗結果
- 4 動态規劃算法
-
- 4.1 動态規劃的設計思想
- 4.2 動态規劃法求解0/1背包問題
- 4.3 算法步驟
- 4.4 代碼實作
- 4.5 優化算法
- 4.6 實驗結果
- 5 動态規劃法和貪婪法對比
- 6 總結
1 背包問題定義
給定一個載重量為M的背包，還有n個重量為wi,價值為pi的物體，1<=i<=n,要求把物體裝滿背包，并且使得背包内物體的價值最大，這類問題稱為背包問題。背包問題還可劃分成兩類，一類是0/1背包問題：物體不可分割，隻能完整的裝入背包，另一類是非0/1問題：物體可以分割成部分裝入背包。本文将用三種算法求解背包問題，并進行對比，三種算法分别是：回溯法，貪婪法和動态規劃法。
2 回溯法
2.1 回溯法的設計思想
回溯法在确定了解空間的結構後，從根結點出發，以深度優先的方式搜尋整個解空間，此時根結點成為一個活結點，并且成為目前的擴充結點。每次都從擴充結點向縱向搜尋新的結點，當算法搜尋到了解空間的任一結點，先判斷該結點是否肯定不包含問題的解（是否還能或者還有必要繼續往下搜尋），如果确定不包含問題的解，就逐層回溯；否則，進入子樹，繼續按照深度優先的政策進行搜尋。當回溯到根結點時，說明搜尋結束了，此時已經得到了一系列的解，根據需要選擇其中的一個或者多個解即可。
回溯法解決問題一般分為三個步驟：
- 針對所給問題，定義問題的解空間。
- 确定易于搜尋的解空間結構。
- 以深度優先的方式搜尋解空間。
2.2 回溯法求解0/1背包問題
假設：xi是物體i被裝入背包的部分，xi =0，1，當xi=0時表示物體i沒有被裝入背包；當xi=1時表示物體i被全部裝入背包。根據問題的要求，可以構造下面的限制方程和目标函數：
KaTeX parse error: Unknown column alignment: * at position 16: \begin{array}{*̲{20}{l}}{{\math…
于是問題可以歸結為尋找一個滿足限制方程（1），并使得目标函（2）達到最大值的解向量 X=（x1,x2,x3,x4,…,xn)。回溯法搜尋這個解向量X時，狀态空間樹是一個高度為n的完全二叉樹，其節點總數是2^(n+1) -1.從根節點到葉子節點的所有路徑，描述了問題解的所有可能狀态。
首先約定：第i層的左兒子子樹描述物體vi被裝入背包的情況，右兒子子樹描述物體vi未被裝入背包的情況。
在狀态空間樹的搜尋過程中，一方面可以通過限制方程（5）來控制不需要通路的節點，另一方面還可以利用目标函數（6）來進一步控制不需要通路的節點的個數。初始化時把目标函數的上界初始化為0，把物體按價值重量比的非增順序排列，然後按照這個順序搜尋；盡量沿着左兒子節點前進，當不能沿着左兒子節點繼續前進時，說明得到了問題的一個部分解。然後把搜尋轉移到右兒子子樹。此時，估計這個部分解所能得到的最大價值，把該值和目前的上界進行對比，如果該值大于目前上界，就繼續由右兒子樹向下搜尋，擴大這部分解，直到找到一個可行解。最後把可行解儲存起來，用目前可行解的值重新整理目标函數的上界，并向上回溯，尋找其他可行解；如果由部分解所估計的最大值小于目前上界，就丢棄目前正在搜尋的部分解，直接向上回溯。
2.3 算法步驟
假設目前的部分解是{x0,x1,…,xk-1}，同時有：
KaTeX parse error: Unknown column alignment: * at position 17: …{\begin{array}{*̲{20}{l}} {{\mat…
式子（7）表示裝入第k個物體之前，背包尚有空餘的載重量，繼續裝入物體k之後，将超過背包的載重量。由此得到部分解{x0,x1,…,xk}，其中xk=0。由這個部分解繼續向下搜尋将有：
KaTeX parse error: Unknown column alignment: * at position 17: …{\begin{array}{*̲{20}{l}} {{\mat…
式子（8）表示，不裝入第k個物體，繼續裝入k+1,k+2…k+m-1的物體，背包尚有空餘的載重量，但是繼續裝入第k+m個物體之後，将超過物體的載重量。因為物體是按照價值重量比按非增順序排列的，是以這個部分解還可以繼續向下搜尋。能找到的可能解的最大值不會超過：
∑ i = 0 k x i p i + ∑ i = k + 1 k + m − 1 x i p i + ( M − ∑ i = 0 k x i w i − ∑ i = 0 k + m − 1 x i w i ) × p k + m / w k + m ( 9 ) {{\mathop{ \sum }\limits_{{i=0}}^{{k}}{\mathop{{x}}\nolimits_{{i}}\mathop{{p}}\nolimits_{{i}}}}+{\mathop{ \sum }\limits_{{i=k+1}}^{{k+m-1}}{\mathop{{x}}\nolimits_{{i}}\mathop{{p}}\nolimits_{{i}}}}+{ \left( {M-{\mathop{ \sum }\limits_{{i=0}}^{{k}}{\mathop{{x}}\nolimits_{{i}}\mathop{{w}}\nolimits_{{i}}}}-{\mathop{ \sum }\limits_{{i=0}}^{{k+m-1}}{\mathop{{x}}\nolimits_{{i}}\mathop{{w}}\nolimits_{{i}}}}} \right) } \times \mathop{{p}}\nolimits_{{k+m}}/\mathop{{w}}\nolimits_{{k+m}}}(9) i=0∑kxipi+i=k+1∑k+m−1xipi+(M−i=0∑kxiwi−i=0∑k+m−1xiwi)×pk+m/wk+m(9)
如果目前搜尋到目前結點，它的最大價值估計值小于目前目标函數上界，則放棄向下搜尋，進行回溯。如果目前結點是左兒子子樹結點，則轉向相應的右兒子子樹結點進行搜尋；如果目前結點是右兒子子樹結點，則退回父節點。
用回溯法求解0/1背包問題可以概括為以下10個步驟：
- 把物體按價值重量比按照遞減的順序排列。
- 把w_cur（目前背包物體的總重量）、p_cur（目前背包物體的總價值）和p_total（所有可行解的最大價值）初始化為0，解向量的各個分量初始化為0，搜尋樹的搜尋深度k置為0 。
- 令p_est（目前部分解可能達到的最大價值的估計值） = p_cur，對滿足k<=i<n的所有i，按照式子（8）（9）更新從目前的部分解可取的的最大價值估計值p_est。
- 如果p_est > p_total，轉步驟5，否則轉步驟8.
- 從vk開始把物體裝入背包，直到沒有物體可裝入或者裝不下物體vi為止，并生成部分解yk,…,yi，k<=i<n，重新整理p_cur。
- 如果i>=n-1，則得到一個新的可行解，用可行解更新解向量X，更新p_total=p_cur。轉步驟3，以便回溯到其他可行解，否則得到一個部分解，轉步驟7
- 令k=i+1，舍棄物體vi，轉步驟3，以便可以從物體v(k+1)繼續裝入。
- 當i>=0并且yi=0時，執行i=i-1，直到yi=1為止；即沿着右兒子分支節點方向向上回溯，直到回到相應的左兒子分支節點。
- 如果i<0,算法結束，否則轉步驟10 。
- 令yi=0，w_cur=w-cur - wi，p_cur = p_cur - pi，k=i+1，轉步驟3 。
2.4 代碼實作
typedef struct {
float w; /*物體重量*/
float p; /*物體價值*/
float v; /*物體價值重量比*/
} Object;
Object ob[n]; /*n個物體下資訊*/
float M; /*背包載重量*/
int x[n]; /*可能的向量解*/
int y[n]; /*目前搜尋的解向量*/
float p_eat; /*目前搜尋方向部分解的最大價值估計值*/
float p_total;
float w_cur;
float p_cur;
float knapsack_back(Object ob[],float M,int n,int x[]) {
float w_cur, p_total,p_cur,w_eat,p_eat;
int *y = new int[n+1];
for (int i = 0; i < n; i++) {
ob[i].v = ob[i].p /ob[i].w;
y[i] = 0;
}
merge_sort(ob, n); /*物體按照價值重量比的非增順序排列*/
w_cur = p_cur = p_total = 0;
y[n] = 0;
k = 0;
while (k<=n) {
w_est = w_cur;
p_est = p_cur;
for (int i = k; i< n;i++) { /*沿着目前分支搜尋*/
w_est += ob[i].w;
if (w_est<M) {
p_est += ob[i].p;
} else {
p_est += (M - w_est+ob[i].w)/ob[i].w * ob[i].p;
break;
}
}
if (p_est > p_total) { /*估計值大于上界*/
for (int i = k;i<n; i++) {
if (w_cur + ob[i].w <= M) { /*可裝入第i個物體*/
w_cur += ob[i].w;
p_cur += ob[i].p;
y[i] = 1;
} else {
y[i] = 0; /*不能裝入第i個物體*/
break;
}
}
if(i >= n-1) { /*n個物體已經全部裝入*/
if (p_cur > p_total) {
p_total = p_cur; /*重新整理目前上限*/
k = n;
for (int j = 0; j < n; j++) /*儲存可能的解*/
x[j] = y[j];
}
} else
k = i+1; /*繼續裝入其他物體*/
} else { /*估計值小于目前上限*/
while ((k >= 0) && (y[k] != 0)) /*沿着右分支節點方向回溯*/
k = k-1; /*直到左分支節點*/
if (k<0) break; /*到根節點，則結束*/
else {
w_cur = w_cur - ob[k].w;
p_cur = p_cur - ob[k].p;
y[k] = 0; k += 1;
}
}
}
delete y;
return p_total;
}
2.5 實驗結果
輸入：物體數量為5，背包載重量為50，背包的價值分别是（40，45，44，50，45），背包的重量分别是（10，15，20，25，30）。
理論上輸出：背包最大價值139，裝入背包的物體為（0，1，1，1，0）。
2.5.1 回溯法求解背包問題的搜尋樹
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-G2Evpl6c-1580817786560)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107174612211.png)]
2.5.2 搜尋樹生成過程
- 開始時，目标函數的上界p_total初始化為0，計算從根節點開始搜尋所取得的最大估計值p_est=159, 大于p_total，是以向下生成節點1，2，3，4，得到部分解（1，1，1，0）。
- 結點4是右兒子分支結點，于是估計從結點4開始向下搜尋可取得的最大值p_est=151.5，大于p_total，是以繼續向下搜尋生成結點5，得到最大價值129，更新p_total=129，将可行解=（1，1，1，0，0）儲存在解向量X中。
- 由葉子結點5繼續搜尋，估計可能取得的最大值為129，不大于p_total，是以向上回溯k–，直到yk=1到達結點3，并生成相應的右兒子分支結點6，得到部分解（1，1，0）。
- 計算從結點6開始搜尋可取得的最大價值估計值p_est=155，大于p_total，是以向下繼續搜尋生成結點7、8。并生成最大價值p_cur=135，取得的可行解為（1，1，0，1，0），并更新p_total = p_cur=135。同時用這個可行解更新解向量X中的内容。
- 由結點8繼續搜尋，計算其最大價值估計值為135，不大于p_total，是以向上回溯，直到yk=1，回到結點7，并生成相應的右兒子分支結點9，得到部分解（1，1，0，0）。
- 計算從結點9搜尋所取得的最大價值估計值為137.5，大于p_total=135，是以繼續向下搜尋生成結點10，得到最大價值p_cur=130，小于p_total的值，是以p_total和解向量X均未更新。因為結點10是左兒子結點，是以向前回溯後生成其相應的右兒子分支結點11，得到最大價值為85，小于p_total的值，是以p_total和解向量X均未更新。
- 由葉子結點11繼續搜尋，計算其最大價值估計值為85，小于p_total，是以沿着右兒子分支結點的方向向上回溯，直到結點2，生成其相應的右兒子分支結點12，得到部分解（1，0）。
- 計算從結點12向下搜尋可取得的最大價值估計值為190，是以向下搜尋生成結點13，14，15。得到最大價值為134，小于p_total，是以解向量X和p_total值均未更新。
- 由葉子結點15繼續搜尋，計算最大價值估計值為134，小于p_total，是以沿着右兒子分支結點方向向上回溯，到達結點13，生成其對應的右兒子分支結點16，由于結點16是右分支結點，計算其最大價值估計值為129，小于p_total ，是以沿着右兒子分支結點向上回溯，到達結點13，生成其對應的右兒子分支結點17，計算從結點17繼續搜尋可取得的最大價值估計值為140，是以可以沿着結點17向下搜尋，生成結點18，19。得到的最大價值p_cur為90，小于p_total，是以解向量X和p_est均未更新。
- 由葉子結點19繼續搜尋，計算可取得的最大價值估計值p_est為90，小于p_total，是以沿着右兒子分支結點方向向上回溯，直到結點18，生成其相應的右兒子結點20，計算從結點20開始搜尋可取得的最大價值估計值p_est=115，小于p_total，是以繼續向上回溯，回到結點1，生成其相應的右兒子結點21。計算從結點21繼續搜尋可取得的最大價值估計值為180，是以繼續向下搜尋生成結點22、23、24、25。得到最大價值為139，大于p_total，是以更新p_total=139，得到可行解（0，1，1，1，0），用該可行解更新解向量X。
- 由葉子結點25繼續搜尋，計算可取得的最大價值估計值為139，不大于p_total，是以向上回溯回到結點24，生成其相應的右兒子分支節點26，計算從結點26搜尋可取得的最大價值估計值為131.5小于p_total，是以繼續向上回溯，回到結點23，生成其對應的右兒子分支結點27，計算從結點27搜尋可取得的最大價值估計值為115小于p_total，是以繼續向上回溯，回到結點22，生成其對應的右兒子分支結點28，計算從結點28搜尋可取得的最大價值估計值為132小于p_total，是以繼續向上回溯，回到結點0.算法結束。
2.5.3實際輸出：
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-HfHbqeZw-1580817786561)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107202953581.png)]
實驗證明，回溯法可以求得0/1背包問題的最優解，但是它的時間複雜度和空間複雜度在最壞的情況下為O(2^n)。
2.6 回溯算法的效率分析
回溯算法的效率和以下幾個因素有關：
- 生成節點所花費的時間
- 計算限制方程所花費的時間
- 計算目标函數的界所花費的時間
- 所生成節點的個數
回溯算法的運作時間取決于搜尋過程中它生成的結點數。不同的搜尋方式所生成的結點數是不同的。用回溯算法求解背包問題時，最壞的情況下，所搜尋的結果是一棵滿二叉樹，時間複雜度為o(2^n)，每次還要對是否将n個物體裝入背包進行比較，時間複雜度為O(n)， 是以最壞情況下回溯算法是時間複雜度是O(n*2^n)。
3 貪婪算法
3.1 貪婪法的設計思想
貪婪法一般由一個疊代的循環組成，在每一輪循環中，通過少量的局部的計算，尋找出一個局部最優解。是以它是通過一步步地尋找局部最優解來試圖建立問題的最終解。貪婪法的每一步的工作都增加了部分解的規模，每一步的選擇也都極大增長了它所希望實作的目标函數。正因如此，在很多執行個體中，利用貪婪算法所産生的局部最優解最終都能建立問題的全局最優解。
貪婪法有兩個很重要的性質：
-
貪婪選擇性質
所謂貪婪選擇性質，是指所求問題的最優解可以通過一系列局部最優解的選擇來達到。每進行一次選擇就能得到一個局部的解，把所求問題的解簡化成一個規模更小的類似子問題。
-
最優子結構性質
最優子結構是指一個問題的最優解包含其子問題的最優解。
3.2 貪婪法解決部分背包問題
背包問題分為兩種情況，一種情況是每個物體都是完整的裝入背包即0/1背包問題，另一種情況是物體可以分部分裝入背包，本節讨論的正是第二種情況。
假設：xi是物體i被裝入背包的部分，0 <= xi <= 1，當xi=0時表示物體i沒有被裝入背包；當xi=1時表示物體i被全部裝入背包。根據問題的要求，可以構造下面的限制方程和目标函數：
KaTeX parse error: Unknown column alignment: * at position 16: \begin{array}{*̲{20}{l}} {{\mat…
于是問題可以歸結為尋找一個滿足限制方程（1），并使得目标函（2）達到最大值的解向量 X=（x1,x2,x3,x4,…,xn)。
解決方案是：優先選擇價值pi最大的物體裝入背包，直到最後一個物體裝不下時，選擇一個适當的物體分割成部分xi<1裝入背包。但是采取這種方法不一定能達到最優解，因為如果選擇的物體的重量很大，那麼背包很快就被裝滿，使得其他價值高的物體無法繼續裝入，最終背包的價值并不是最大的。是以，本文所選擇的政策都是先計算每個物體的價值重量比，然後将比值大的物體優先裝入背包。
3.2.1 算法設計：
首先定義物體的結構體：
typedef struct {
float p; /*物體的價值*/
float w; /*物體的重量*/
float v; /*物體的價值重量比*/
}
貪心算法的核心代碼如下：
float knapsack_greedy(float M, OBJECT ob[],float x[], int N) {
float m,p=0;
int n = N;
for (int i = 0; i < n; i++) {
ob[i].v = ob[i].p /ob[i].w;
x[i] = 0;
}
merge_sort(ob, n); /*重新給物體排序，價值重量比大的物體排在前面*/
m = M;
for (int i = 0; i < n; i++) {
if (ob[i].w <= m) {
x[i] = 1;
m -= ob[i].w;
p += ob[i].p;
} else {
x[i] = m/ob[i].w; /*當最後一個物體重量比背包剩餘載重量大時，将物體劃分成一定比例裝入背包*/
p += x[i]*ob[i].p;
break;
}
}
return p;
}
3.2.2 實驗結果
輸入：物體數量為5，背包載重量為60，背包的價值分别是（40，45，44，50，45），背包的重量分别是（10，15，20，25，30）。
理論上輸出：背包最大價值159，裝入背包的物體為（1，1，1，0.6，0）。
實際輸出：
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-jIPC8Ed4-1580817786561)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107114432242.png)]
輸入：物體數量為3，背包載重量為50，背包的價值分别是（60，100，120），背包的重量分别是（10，20，30）。
理論上輸出：背包最大價值240，裝入背包的物體為（1，1，0.67）。
實際輸出：
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-Telqk8DO-1580817786561)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200106162748602.png)]
從實驗結果可以看出，按照貪婪法的運算步驟可以找到背包問題的最優解。
3.3貪婪算法解決0/1背包問題
假設：xi是物體i被裝入背包的部分，xi =0，1，當xi=0時表示物體i沒有被裝入背包；當xi=1時表示物體i被全部裝入背包。根據問題的要求，可以構造下面的限制方程和目标函數：
KaTeX parse error: Unknown column alignment: * at position 16: \begin{array}{*̲{20}{l}}{{\math…
于是問題可以歸結為尋找一個滿足限制方程（1），并使得目标函（2）達到最大值的解向量 X=（x1,x2,x3,x4,…,xn)。
3.3.1 算法設計
定義資料結構：
typedef struct {
float p; /*物體的價值*/
float w; /*物體的重量*/
float v; /*物體的價值重量比*/
}
輸入：背包載重量M，物體的價值p，物體的重量w，物體的個數n。
輸出：n個物體被裝入背包的分類x[]，背包中物體的總價值。
核心代碼如下：
float knapsack_greedy(float M, OBJECT ob[],float x[], int N) {
float m,p=0;
int n = N;
for (int i = 0; i < n; i++) {
ob[i].v = ob[i].p /ob[i].w;
x[i] = 0;
}
merge_sort(ob, n); /*重新給物體排序，價值重量比大的物體排在前面*/
m = M;
for (int i = 0; i < n; i++) {
if (ob[i].w <= m) {
x[i] = 1;
m -= ob[i].w;
p += ob[i].p;
} else { /*當最後一個物體重量大于背包剩餘載重量時，不再繼續放入物體*/
break;
}
}
return p;
}
3.3.2 實驗結果
輸入：物體數量為5，背包載重量為60，背包的價值分别是（40，45，44，50，45），背包的重量分别是（10，15，20，25，30）。
理論上輸出：背包最大價值139，裝入背包的物體為（0，1，1，1，0）。
實際輸出：
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-k4UweA3j-1580817786563)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107114702514.png)]
輸出的129并不是背包能裝入的最大價值，如果隻裝重量為12，20和25的物體，那麼背包價值是可達139，比用貪婪法求得的價值要高很多。是以貪心算法不能解決0/1背包問題。
4 動态規劃算法
4.1 動态規劃的設計思想
動态規劃和分治算法類似，其基本思想就是将問題劃分為若幹個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。
動态規劃算法的有兩個重要的性質：
- 最優子結構性質：即問題的最優解包含子問題的最優解。由每一步的子問題的最優解最終生成問題的最優解。
- 重疊子問題性質：動态規劃求解問題時，每次産生的子問題并不總是新的子問題，有些子問題被重複計算多次，這種性質稱為重疊子問題。解決方法：将已求得的子問題的解儲存起來，避免重複計算相同的子問題。
4.2 動态規劃法求解0/1背包問題
假設：xi是物體i被裝入背包的部分，xi =0，1，當xi=0時表示物體i沒有被裝入背包；當xi=1時表示物體i被全部裝入背包。根據問題的要求，可以構造下面的限制方程和目标函數：
KaTeX parse error: Unknown column alignment: * at position 16: \begin{array}{*̲{20}{l}}{{\math…
于是問題可以歸結為尋找一個滿足限制方程（1），并使得目标函（2）達到最大值的解向量 X=（x1,x2,x3,x4,…,xn)。
這個問題也可以用動态規劃分階段決策的方法，來确定把哪個物體裝入背包的最優決策。構造下面的動态規劃函數：
KaTeX parse error: Unknown column alignment: * at position 17: …{\begin{array}{*̲{20}{l}} {{\mat…
式子（3）表明把前面i個物體裝入載重為0 的背包，或者把0個物體裝入載重為j的背包，其價值都為0.式子（4）的第一個式子表明：如果第i個物體裝入載重量為j的背包，則背包裝入前i個物體的總價值和裝入前i-1個物體的總價值一樣。（4)的第二個式子表明，如果第i個物體的重量小于背包的載重量，則背包裝入前i個物體的總價值等于将前i-1個物體裝入載重量為（j-wi）的背包所得到的價值量加上物體i的價值pi。如果第i個物體沒有裝入背包，則背包中的物體價值等于将前i-1個物體裝入載重量為j的背包所得的價值。
4.3 算法步驟
設optpn(m)是載重量為m的背包，裝入n個物體時得到的最大價值。為了确定裝入背包的具體物品，從optpn(m)的值向前倒推，如果optpn(m)大于optp(n-1)(m)，說明第n個物品被裝入了背包，則下一步确定把前n-1個物體裝入載重量為m-wn的背包中；如果optpn(m)小于等于optp(n-1)(m)，說明第n個物品沒有被裝入了背包，則下一步确定把前n-1個物體裝入載重量為m的背包中。
算法具體步驟如下：
- 初始化，對滿足0<=i<=n,0<=j<=m的i和j，令式子（3）成立。
- 令i=1.
- 對滿足0<=j<=m的j，按照式子（4）計算optpi(j)。
- i=i+1，若i>n，轉步驟5，否則轉步驟3。
- 令i=n，j=m。
-
按照
KaTeX parse error: Unknown column alignment: * at position 17: …{\begin{array}{*̲{20}{l}} {\begi…
求第i個分量xi
- i=i-1，若i>0，則轉步驟（6），否則算法結束。
4.4 代碼實作
//動态規劃表
int optp[N][N];
for (int i = 0; i <= n; i++) {
optp[i][0] = 0;
x[i] = 0;
}
for (int j = 0; j <= M; j++) optp[0][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= M; j++) {
if (j < w[i])
optp[i][j] = optp[i - 1][j];
else {
optp[i][j] = max(optp[i - 1][j], optp[i - 1][j - w[i]] + p[i]);
}
}
}
時間複雜度為O(n*m)
4.5 優化算法
由狀态轉移方程（4）可知，optp[i] [j]的值僅僅和optp[i] [j-w[i]]和optp[i-1] [j]的值相關，是以可以将上述的二維矩陣優化成為一維矩陣，減少空間複雜度。優化之後，狀态轉移方程變為optp[i] [j] = max ( optp[i] [j-w[i]], optp[i-1] [j] )。
核心代碼如下：
//優化動态規劃
int optp[M];
for (int i = 0; i <= M; i++) {
optp[i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = M; j >= w[i]; j--) {
optp[j] = max(optp[j], optp[j - w[i]] + p[i]);
}
}
}
優化之後，算法的時間複雜度和空間複雜度都是O(n*m)，而空間複雜度優化為O(m)。
4.6 實驗結果
輸入：物體數量為5，背包載重量為10，背包的價值分别是（6，3，5，4，6），背包的重量分别是（2，2，6，5，4）。
理論上輸出：背包最大價值15，裝入背包的物體為（1，1，0，0，1）。
動态規劃的計算步驟表如下：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| 2 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
| 3 | 6 | 6 | 9 | 9 | 9 | 9 | 11 | 11 | 14 |
| 4 | 6 | 6 | 9 | 9 | 9 | 10 | 11 | 13 | 14 |
| 5 | 6 | 6 | 9 | 9 | 12 | 12 | 15 | 15 | 15 |
實際輸出：
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-TDBkw0XN-1580817786564)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200106195740745.png)]
輸入：物體數量為5，背包載重量為60，背包的價值分别是（40，45，44，50，45），背包的重量分别是（10，15，20，25，30）。
理論上輸出：背包最大價值139，裝入背包的物體為（0，1，1，1，0）。
實際輸出：
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-hglMDrl7-1580817786564)(C:\Users\86188\AppData\Roaming\Typora\typora-user-images\image-20200107115212809.png)]
上述實驗證明，動态規劃方法可以求解0/1背包問題的最優解。
5 動态規劃法和貪婪法對比
共同點：問題具有最優子結構特征，能從子問題的最優解找到原問題的最優解。
不同點：
- 動态規劃方法尋找問題最優解時依賴所有子問題的解。而貪心算法從一個局部解開始擴充，作出最優選擇後得到一個新的子問題，所作的選擇隻依賴過去所作的選擇，直到找到整體最優解。
- 貪婪法産生的結構圖，所作的選擇隻依賴于過去所作的選擇：
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-RsWF4z6R-1580817786564)(C:\Users\86188\Desktop\貪心算法.png)]
動态規劃産生的結構圖，它依賴于所有子問題的解：
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-WbP1qvQk-1580817786565)(C:\Users\86188\Desktop\動态規劃.png)]
- 貪心算法的時間複雜度和空間複雜度都是O(n^2)，空間複雜度可以優化為O(n)；動态規劃的時間複雜度是O(n*m)，空間複雜度可以優化為O(m)。
- 貪心算法不能求解0/1背包問題，隻能求解部分背包問題。而動态規劃法既可以求解部分背包問題，也可以求解0/1背包問題。
6 總結
背包問題的三個算法對比，貪婪法隻能解決部分背包問題，不能解決0/1背包問題，因為用貪婪法每次裝入價值高的物體，背包很快就不能繼續裝入其他物體，最終的總價值并不是最大的。但是貪婪法在選擇背包之前要對物體的價值重量比進行排序，是以貪婪法的時間複雜度是O(n^2)。動态規劃法既能解決部分背包問題也能解決0/1背包問題，而且動态規劃法在選擇物體裝入時，不需要對物體的價值重量比進行排序，時間複雜度為O(n*m)。回溯法在求解背包問題上效率并不高。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)