動態(tài)規(guī)劃在背包問題的應(yīng)用一、動態(tài)規(guī)劃概述

動態(tài)規(guī)劃（DynamicProgramming，DP）是一種通過將復(fù)雜問題分解為子問題并存儲子問題解來優(yōu)化遞歸算法的算法思想。它適用于具有以下特征的優(yōu)化問題：

1.最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解包含子問題的最優(yōu)解。

2.重疊子問題：不同決策路徑可能重復(fù)計算相同的子問題。

動態(tài)規(guī)劃通常使用表格（一維或二維）存儲中間結(jié)果，避免重復(fù)計算，顯著提高效率。

二、背包問題及其分類

背包問題是一類典型的優(yōu)化問題，通常描述為：給定一組物品，每個物品有重量和價值，背包有最大承重限制，如何選擇物品裝入背包，使背包內(nèi)物品總價值最大，同時不超過承重限制。

（一）背包問題分類

1.0/1背包問題：每個物品只能選擇0個或1個。

2.完全背包問題：每個物品可以無限次選擇。

3.多重背包問題：每個物品有數(shù)量限制，可以選擇0個或多個。

本節(jié)主要討論0/1背包問題，其他類型可類似擴展。

三、0/1背包問題的動態(tài)規(guī)劃解法

（一）問題定義

-輸入：

-物品數(shù)量\(n\)

-背包最大承重\(W\)

-每個物品的重量\(w[i]\)和價值\(v[i]\)

-輸出：背包能裝下的最大價值。

（二）動態(tài)規(guī)劃狀態(tài)定義

定義二維數(shù)組\(dp[i][j]\)表示：

-狀態(tài)含義：前\(i\)個物品，背包容量為\(j\)時能裝下的最大價值。

（三）狀態(tài)轉(zhuǎn)移方程

對于第\(i\)個物品，有兩種選擇：

1.不選擇第\(i\)個物品：

\(dp[i][j]=dp[i-1][j]\)

2.選擇第\(i\)個物品（前提是\(j\geqw[i]\)）：

\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)

最終狀態(tài)轉(zhuǎn)移方程為：

\[dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])\]

（四）算法步驟

1.初始化：

-\(dp[0][j]=0\)：沒有物品時，價值為0。

-\(dp[i][0]=0\)：背包容量為0時，價值為0。

2.填充表格（按行或按列順序遍歷）：

-對于每個物品\(i\)和容量\(j\)，計算\(dp[i][j]\)。

3.結(jié)果：

-最終答案為\(dp[n][W]\)。

（五）空間優(yōu)化

由于每次計算僅依賴上一行數(shù)據(jù)，可以將二維數(shù)組優(yōu)化為一維數(shù)組，降低空間復(fù)雜度。

四、示例計算

假設(shè)：

-物品數(shù)量\(n=4\)

-背包容量\(W=7\)

-物品重量\(w=[3,2,5,1]\)

-物品價值\(v=[10,5,15,10]\)

（一）動態(tài)規(guī)劃表格填充

|物品|容量|0|1|2|3|4|5|6|7|

|------|-------|---|---|---|---|---|---|---|---|

|0|0|0|0|0|0|0|0|0|0|

|1|0|0|0|0|0|0|0|0|0|

|1|1|0|0|0|0|0|0|0|0|

|1|2|0|0|0|0|0|0|0|0|

|1|3|0|0|0|5|5|5|5|5|

|1|4|0|0|0|5|5|5|5|5|

|1|5|0|0|5|5|5|10|10|10|

|1|6|0|0|5|5|10|10|10|10|

|1|7|0|0|5|10|10|10|15|15|

（二）最終結(jié)果

最大價值為\(dp[4][7]=15\)，對應(yīng)選擇物品2（價值15，重量5）。

五、總結(jié)

動態(tài)規(guī)劃通過分解子問題并存儲結(jié)果，有效解決了背包問題的優(yōu)化需求。關(guān)鍵在于：

1.明確狀態(tài)定義和轉(zhuǎn)移方程。

2.選擇合適的表格或空間優(yōu)化方式。

3.注意邊界條件的處理。

類似方法可擴展到其他組合優(yōu)化問題。

三、0/1背包問題的動態(tài)規(guī)劃解法（續(xù)）

（一）動態(tài)規(guī)劃狀態(tài)定義（詳細說明）

動態(tài)規(guī)劃的核心在于將原問題轉(zhuǎn)化為子問題。對于0/1背包問題，定義：

-狀態(tài)表示：用二維數(shù)組\(dp[i][j]\)表示“前\(i\)個物品”在“背包容量為\(j\)時”所能獲得的最大價值。

-維度解釋：

-\(i\)：物品索引，從0到\(n-1\)（假設(shè)物品編號從0開始）。

-\(j\)：當前背包剩余容量，從0到\(W\)（\(W\)為背包總?cè)萘浚?/p>

-狀態(tài)含義：

-\(dp[i][j]\)存儲的是基于前\(i\)個物品和當前背包容量\(j\)的最優(yōu)解（即最大價值）。

-最終答案為\(dp[n][W]\)，即考慮所有\(zhòng)(n\)個物品且背包容量為\(W\)時的最大價值。

（二）狀態(tài)轉(zhuǎn)移方程（深入解析）

狀態(tài)轉(zhuǎn)移是動態(tài)規(guī)劃的關(guān)鍵，其本質(zhì)是選擇當前物品的最優(yōu)決策。對于第\(i\)個物品，有兩種選擇：

1.不選擇第\(i\)個物品：

-此時，背包容量不變，仍考慮前\(i-1\)個物品。

-狀態(tài)轉(zhuǎn)移：\(dp[i][j]=dp[i-1][j]\)

-解釋：如果不選第\(i\)個物品，最大價值直接繼承自前\(i-1\)個物品在容量\(j\)下的最大價值。

2.選擇第\(i\)個物品：

-前提條件：當前背包容量\(j\)必須足夠裝下第\(i\)個物品（即\(j\geqw[i]\)）。

-操作：

-將第\(i\)個物品裝入背包，消耗容量\(w[i]\)。

-剩余容量為\(j-w[i]\)，此時考慮前\(i-1\)個物品的最大價值，并加上第\(i\)個物品的價值\(v[i]\)。

-狀態(tài)轉(zhuǎn)移：\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)

-解釋：選擇第\(i\)個物品后，最大價值等于“剩余容量\(j-w[i]\)下的最大價值”加上“當前物品價值\(v[i]\)”。

3.決策選擇：

-對于當前狀態(tài)\(dp[i][j]\)，需要比較上述兩種選擇的結(jié)果，取較大值：

\[dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])\]

-邏輯：在容量\(j\)下，對于第\(i\)個物品，最優(yōu)策略是“不選”或“選”，選哪個取決于哪種方式帶來的價值更大。

（三）算法步驟（分步詳解）

動態(tài)規(guī)劃算法的實現(xiàn)分為以下幾步：

(1)初始化表格

-創(chuàng)建二維數(shù)組\(dp[n+1][W+1]\)，所有元素初始化為0。

-原因：

-\(dp[0][j]=0\)：沒有物品時（\(i=0\)），無論容量多少，價值都為0。

-\(dp[i][0]=0\)：容量為0時（\(j=0\)），無法裝任何物品，價值為0。

-注意：索引從0開始，因此需要\(dp[n+1][W+1]\)以覆蓋所有情況。

(2)填充表格（按行或按列遍歷）

-遍歷順序：通常按物品編號\(i\)從小到大，背包容量\(j\)從小到大遍歷。

-每一步的操作：

-對于當前物品\(i\)和當前容量\(j\)，根據(jù)狀態(tài)轉(zhuǎn)移方程計算\(dp[i][j]\)：

\[dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])\]

-條件判斷：

-如果\(j<w[i]\)，則無法選擇第\(i\)個物品（容量不足），此時\(dp[i][j]=dp[i-1][j]\)。

-如果\(j\geqw[i]\)，則比較“不選”和“選”兩種情況。

-示例：

-以第2個物品（\(i=1\)）、容量\(j=3\)為例：

-\(j<w[1]\)（即3<2）？否，繼續(xù)計算。

-\(dp[1][3]=\max(dp[0][3],dp[0][3-2]+v[1])\)

-\(dp[1][3]=\max(0,0+5)=5\)

(3)獲取最終結(jié)果

-最終最大價值存儲在\(dp[n][W]\)中。

-可選：如果需要知道具體選擇了哪些物品，可以回溯表格：

-從\(dp[n][W]\)開始，檢查\(dp[i][j]\)和\(dp[i-1][j]\)的關(guān)系：

-如果\(dp[i][j]=dp[i-1][j]\)，則第\(i\)個物品未被選擇。

-如果\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)，則第\(i\)個物品被選擇，記錄該物品。

-繼續(xù)回溯\(i-1\)，直到\(i=0\)。

（四）空間優(yōu)化（降維打擊）

二維數(shù)組雖然直觀，但空間復(fù)雜度為\(O(nW)\)，對于大\(n\)或\(W\)可能不高效。通過觀察狀態(tài)轉(zhuǎn)移方程，可以發(fā)現(xiàn)：

-計算\(dp[i][j]\)只依賴于第\(i-1\)行的數(shù)據(jù)（即\(dp[i-1][\cdot]\)）。

-因此，可以將二維數(shù)組優(yōu)化為一維數(shù)組，按容量\(j\)從小到大的順序計算。

優(yōu)化步驟：

1.創(chuàng)建一維數(shù)組\(dp[W+1]\)，初始化為0。

2.按物品遍歷：對于每個物品\(i\)，從大到小更新\(dp[j]\)（即從\(W\)到\(w[i]\)逐步減少容量）：

\[dp[j]=\max(dp[j],dp[j-w[i]]+v[i])\]

-原因：按容量從大到小更新可以避免重復(fù)計算。

3.最終結(jié)果仍為\(dp[W]\)。

示例：

-物品：\(w=[3,2,5,1]\),\(v=[10,5,15,10]\),\(W=7\)。

-初始化：\(dp=[0,0,0,0,0,0,0,0]\)。

-第1個物品（\(i=0\)）：

-更新\(j=7,6,5,4,3\)：

-\(dp[7]=\max(0,dp[4]+10)=10\)

-\(dp[6]=\max(0,dp[4]+10)=10\)

-\(dp[5]=\max(0,dp[3]+10)=10\)

-\(dp[4]=\max(0,dp[1]+10)=10\)

-\(dp[3]=\max(0,dp[0]+10)=10\)

-更新后：\(dp=[0,0,0,0,10,10,10,10]\)。

-第2個物品（\(i=1\)）：

-更新\(j=7,6,5,4\)：

-\(dp[7]=\max(10,dp[5]+5)=15\)

-\(dp[6]=\max(10,dp[4]+5)=15\)

-\(dp[5]=\max(10,dp[3]+5)=15\)

-\(dp[4]=\max(10,dp[2]+5)=10\)

-更新后：\(dp=[0,0,0,5,10,15,15,15]\)。

-最終結(jié)果：\(dp[7]=15\)。

（五）時間與空間復(fù)雜度

-時間復(fù)雜度：\(O(nW)\)

-每個物品和每個容量都計算一次。

-空間復(fù)雜度：

-二維數(shù)組：\(O(nW)\)。

-一維數(shù)組優(yōu)化后：\(O(W)\)。

四、代碼實現(xiàn)（偽代碼示例）

```pseudo

functionknapsack_01(weights,values,W):

n=length(weights)

dp=arrayofsize(W+1)initializedto0

forifrom0ton-1:

forjfromWdowntoweights[i]:

dp[j]=max(dp[j],dp[j-weights[i]]+values[i])

returndp[W]

五、應(yīng)用場景與擴展

（一）典型應(yīng)用場景

0/1背包問題適用于資源有限、選擇離散的場景，例如：

1.購物選擇：在預(yù)算內(nèi)購買商品，最大化總價值。

2.任務(wù)調(diào)度：在時間或資源限制下，選擇任務(wù)組合以最大化收益。

3.基因組合：在有限資源下，選擇基因片段組合以最大化表達效果。

（二）其他背包問題擴展

動態(tài)規(guī)劃思想可推廣至其他背包類型：

1.完全背包問題：每個物品可無限次選擇。

-狀態(tài)轉(zhuǎn)移：\(dp[j]=\max(dp[j],dp[j-w[i]]+v[i])\)

-需按物品遍歷，但無需逆序更新。

2.多重背包問題：每個物品有數(shù)量限制\(c[i]\)。

-可分解為多個0/1背包問題合并。

-也可用一維數(shù)組，但需調(diào)整遍歷策略。

（三）優(yōu)化技巧

1.排序：按價值密度（\(v[i]/w[i]\)）降序排列物品，可提高填充效率。

2.剪枝：如果當前物品無法提供更大價值，提前終止遍歷。

六、總結(jié)

動態(tài)規(guī)劃通過將問題分解為子問題并存儲結(jié)果，有效解決了背包問題的優(yōu)化需求。關(guān)鍵在于：

1.明確狀態(tài)定義和轉(zhuǎn)移方程。

2.選擇合適的表格或空間優(yōu)化方式。

3.注意邊界條件的處理。

4.可通過排序或剪枝進一步優(yōu)化。

類似方法可擴展到其他組合優(yōu)化問題，如旅行商問題、最長公共子序列等。

一、動態(tài)規(guī)劃概述

動態(tài)規(guī)劃（DynamicProgramming，DP）是一種通過將復(fù)雜問題分解為子問題并存儲子問題解來優(yōu)化遞歸算法的算法思想。它適用于具有以下特征的優(yōu)化問題：

1.最優(yōu)子結(jié)構(gòu)：問題的最優(yōu)解包含子問題的最優(yōu)解。

2.重疊子問題：不同決策路徑可能重復(fù)計算相同的子問題。

動態(tài)規(guī)劃通常使用表格（一維或二維）存儲中間結(jié)果，避免重復(fù)計算，顯著提高效率。

二、背包問題及其分類

背包問題是一類典型的優(yōu)化問題，通常描述為：給定一組物品，每個物品有重量和價值，背包有最大承重限制，如何選擇物品裝入背包，使背包內(nèi)物品總價值最大，同時不超過承重限制。

（一）背包問題分類

1.0/1背包問題：每個物品只能選擇0個或1個。

2.完全背包問題：每個物品可以無限次選擇。

3.多重背包問題：每個物品有數(shù)量限制，可以選擇0個或多個。

本節(jié)主要討論0/1背包問題，其他類型可類似擴展。

三、0/1背包問題的動態(tài)規(guī)劃解法

（一）問題定義

-輸入：

-物品數(shù)量\(n\)

-背包最大承重\(W\)

-每個物品的重量\(w[i]\)和價值\(v[i]\)

-輸出：背包能裝下的最大價值。

（二）動態(tài)規(guī)劃狀態(tài)定義

定義二維數(shù)組\(dp[i][j]\)表示：

-狀態(tài)含義：前\(i\)個物品，背包容量為\(j\)時能裝下的最大價值。

（三）狀態(tài)轉(zhuǎn)移方程

對于第\(i\)個物品，有兩種選擇：

1.不選擇第\(i\)個物品：

\(dp[i][j]=dp[i-1][j]\)

2.選擇第\(i\)個物品（前提是\(j\geqw[i]\)）：

\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)

最終狀態(tài)轉(zhuǎn)移方程為：

\[dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])\]

（四）算法步驟

1.初始化：

-\(dp[0][j]=0\)：沒有物品時，價值為0。

-\(dp[i][0]=0\)：背包容量為0時，價值為0。

2.填充表格（按行或按列順序遍歷）：

-對于每個物品\(i\)和容量\(j\)，計算\(dp[i][j]\)。

3.結(jié)果：

-最終答案為\(dp[n][W]\)。

（五）空間優(yōu)化

由于每次計算僅依賴上一行數(shù)據(jù)，可以將二維數(shù)組優(yōu)化為一維數(shù)組，降低空間復(fù)雜度。

四、示例計算

假設(shè)：

-物品數(shù)量\(n=4\)

-背包容量\(W=7\)

-物品重量\(w=[3,2,5,1]\)

-物品價值\(v=[10,5,15,10]\)

（一）動態(tài)規(guī)劃表格填充

|物品|容量|0|1|2|3|4|5|6|7|

|------|-------|---|---|---|---|---|---|---|---|

|0|0|0|0|0|0|0|0|0|0|

|1|0|0|0|0|0|0|0|0|0|

|1|1|0|0|0|0|0|0|0|0|

|1|2|0|0|0|0|0|0|0|0|

|1|3|0|0|0|5|5|5|5|5|

|1|4|0|0|0|5|5|5|5|5|

|1|5|0|0|5|5|5|10|10|10|

|1|6|0|0|5|5|10|10|10|10|

|1|7|0|0|5|10|10|10|15|15|

（二）最終結(jié)果

最大價值為\(dp[4][7]=15\)，對應(yīng)選擇物品2（價值15，重量5）。

五、總結(jié)

動態(tài)規(guī)劃通過分解子問題并存儲結(jié)果，有效解決了背包問題的優(yōu)化需求。關(guān)鍵在于：

1.明確狀態(tài)定義和轉(zhuǎn)移方程。

2.選擇合適的表格或空間優(yōu)化方式。

3.注意邊界條件的處理。

類似方法可擴展到其他組合優(yōu)化問題。

三、0/1背包問題的動態(tài)規(guī)劃解法（續(xù)）

（一）動態(tài)規(guī)劃狀態(tài)定義（詳細說明）

動態(tài)規(guī)劃的核心在于將原問題轉(zhuǎn)化為子問題。對于0/1背包問題，定義：

-狀態(tài)表示：用二維數(shù)組\(dp[i][j]\)表示“前\(i\)個物品”在“背包容量為\(j\)時”所能獲得的最大價值。

-維度解釋：

-\(i\)：物品索引，從0到\(n-1\)（假設(shè)物品編號從0開始）。

-\(j\)：當前背包剩余容量，從0到\(W\)（\(W\)為背包總?cè)萘浚?/p>

-狀態(tài)含義：

-\(dp[i][j]\)存儲的是基于前\(i\)個物品和當前背包容量\(j\)的最優(yōu)解（即最大價值）。

-最終答案為\(dp[n][W]\)，即考慮所有\(zhòng)(n\)個物品且背包容量為\(W\)時的最大價值。

（二）狀態(tài)轉(zhuǎn)移方程（深入解析）

狀態(tài)轉(zhuǎn)移是動態(tài)規(guī)劃的關(guān)鍵，其本質(zhì)是選擇當前物品的最優(yōu)決策。對于第\(i\)個物品，有兩種選擇：

1.不選擇第\(i\)個物品：

-此時，背包容量不變，仍考慮前\(i-1\)個物品。

-狀態(tài)轉(zhuǎn)移：\(dp[i][j]=dp[i-1][j]\)

-解釋：如果不選第\(i\)個物品，最大價值直接繼承自前\(i-1\)個物品在容量\(j\)下的最大價值。

2.選擇第\(i\)個物品：

-前提條件：當前背包容量\(j\)必須足夠裝下第\(i\)個物品（即\(j\geqw[i]\)）。

-操作：

-將第\(i\)個物品裝入背包，消耗容量\(w[i]\)。

-剩余容量為\(j-w[i]\)，此時考慮前\(i-1\)個物品的最大價值，并加上第\(i\)個物品的價值\(v[i]\)。

-狀態(tài)轉(zhuǎn)移：\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)

-解釋：選擇第\(i\)個物品后，最大價值等于“剩余容量\(j-w[i]\)下的最大價值”加上“當前物品價值\(v[i]\)”。

3.決策選擇：

-對于當前狀態(tài)\(dp[i][j]\)，需要比較上述兩種選擇的結(jié)果，取較大值：

\[dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])\]

-邏輯：在容量\(j\)下，對于第\(i\)個物品，最優(yōu)策略是“不選”或“選”，選哪個取決于哪種方式帶來的價值更大。

（三）算法步驟（分步詳解）

動態(tài)規(guī)劃算法的實現(xiàn)分為以下幾步：

(1)初始化表格

-創(chuàng)建二維數(shù)組\(dp[n+1][W+1]\)，所有元素初始化為0。

-原因：

-\(dp[0][j]=0\)：沒有物品時（\(i=0\)），無論容量多少，價值都為0。

-\(dp[i][0]=0\)：容量為0時（\(j=0\)），無法裝任何物品，價值為0。

-注意：索引從0開始，因此需要\(dp[n+1][W+1]\)以覆蓋所有情況。

(2)填充表格（按行或按列遍歷）

-遍歷順序：通常按物品編號\(i\)從小到大，背包容量\(j\)從小到大遍歷。

-每一步的操作：

-對于當前物品\(i\)和當前容量\(j\)，根據(jù)狀態(tài)轉(zhuǎn)移方程計算\(dp[i][j]\)：

\[dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])\]

-條件判斷：

-如果\(j<w[i]\)，則無法選擇第\(i\)個物品（容量不足），此時\(dp[i][j]=dp[i-1][j]\)。

-如果\(j\geqw[i]\)，則比較“不選”和“選”兩種情況。

-示例：

-以第2個物品（\(i=1\)）、容量\(j=3\)為例：

-\(j<w[1]\)（即3<2）？否，繼續(xù)計算。

-\(dp[1][3]=\max(dp[0][3],dp[0][3-2]+v[1])\)

-\(dp[1][3]=\max(0,0+5)=5\)

(3)獲取最終結(jié)果

-最終最大價值存儲在\(dp[n][W]\)中。

-可選：如果需要知道具體選擇了哪些物品，可以回溯表格：

-從\(dp[n][W]\)開始，檢查\(dp[i][j]\)和\(dp[i-1][j]\)的關(guān)系：

-如果\(dp[i][j]=dp[i-1][j]\)，則第\(i\)個物品未被選擇。

-如果\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)，則第\(i\)個物品被選擇，記錄該物品。

-繼續(xù)回溯\(i-1\)，直到\(i=0\)。

（四）空間優(yōu)化（降維打擊）

二維數(shù)組雖然直觀，但空間復(fù)雜度為\(O(nW)\)，對于大\(n\)或\(W\)可能不高效。通過觀察狀態(tài)轉(zhuǎn)移方程，可以發(fā)現(xiàn)：

-計算\(dp[i][j]\)只依賴于第\(i-1\)行的數(shù)據(jù)（即\(dp[i-1][\cdot]\)）。

-因此，可以將二維數(shù)組優(yōu)化為一維數(shù)組，按容量\(j\)從小到大的順序計算。

優(yōu)化步驟：

1.創(chuàng)建一維數(shù)組\(dp[W+1]\)，初始化為0。

2.按物品遍歷：對于每個物品\(i\)，從大到小更新\(dp[j]\)（即從\(W\)到\(w[i]\)逐步減少容量）：

\[dp[j]=\max(dp[j],dp[j-w[i]]+v[i])\]

-原因：按容量從大到小更新可以避免重復(fù)計算。

3.最終結(jié)果仍為\(dp[W]\)。

示例：

-物品：\(w=[3,2,5,1]\),\(v=[10,5,15,10]\),\(W=7\)。

-初始化：\(dp=[0,0,0,0,0,0,0,0]\)。

-第1個物品（\(i=0\)）：

-更新\(j=7,6,5,4,3\)：

-\(dp[7]=\max(0,dp[4]+10)=10\)

-\(dp[6]=\max(0,dp[4]+10)=10\)

-\(dp[5]=\max(0,dp[3]+10)=10\)

-\(dp[4]=\max(0,dp[1]+10)=10\)

-\(dp[3]=\max(0,dp[0]+10)=10\)

-更新后：\(dp=[0,0,0,0,10,10,10,10