今天我們來講一個重要算法就是DP（動態(tài)規(guī)劃）。
首先，在講這一講之前，我們再看一看之前講的貪心法中的硬幣問題。我們以硬幣問題為例，引入我們今天的主角——動態(tài)規(guī)劃。
前面用貪心法解決的最少硬幣問題，要求硬幣面值是特殊的。而對于任意面值的硬幣問題，就需要用 DP 來徹底解決。
題目描述：有 n 種硬幣，面值分別為V1 ,V2 ,?,Vn ，數量無限。輸入非負整數 S，請你選用硬幣，使其和為
S。要求輸出最少的硬幣組合。
我們先定義一個數組 int cnt[M]，其中 cnt[i] 是金額 i 對應的最少硬幣數量。如果程序能計算出所有的 cnt[i]，0<i<M，那么對輸入的某個金額 i，只要查 cnt[i] 就得到了答案。
那么我們該如何計算 cnt[i] 呢？ cnt[i] 和cnt[i?1] 又是否有關系呢？這里涉及到一個“遞推”的思路，從小問題 cnt[i?1] 的解決遞推到大問題cnt[i] 的解決。小問題的解決能推導出大問題的解決。下面我們以 5 種面值 {1,5,10,25,50} 的硬幣為例，講解從 i?1 到 i 的遞推過程：
（1） 只使用最小面值的 1 分硬幣
初始值cnt[0]=0，其他的 cnt[i] 為無窮大。下面計算cnt[1]。
只用1分硬幣
i=0，cnt[0]=0，表示金額為 0，硬幣數量為 0。在這個基礎上，加一個 1 分硬幣，就前進到金額 i=1，硬幣數量 cnt[1] = cnt[0]+1 = cnt[1-1]+1= 1 的情況。同理， i=2 時，相當于在 cnt[1] 的基礎上加1個硬幣，得到 cnt[2] = cnt[2- 1]+1 = 2。繼續(xù)這個過程，結果是：
我們分析上述過程，可以得到遞推關系：cnt[i] = min(cnt[i], cnt[i - 1] + 1);要認真理解這個遞推過程，確保完全明白哦。這可是 DP 的重要步驟—“狀態(tài)轉移”。
（2）在使用面值1分硬幣的基礎上，增加使用第二大面值的5分硬幣
此時應該從 cnt[5] 開始，因為比 5 分硬幣小的金額，不可能用 5 分硬幣實現。
加上5分硬幣
i=5 分時，相當于在 i=0 的基礎上加一個 5 分硬幣，得到 cnt[5] = cnt[5 - 5] + 1 = 1。而 cnt[5] 也可以是在 i=4 的基礎上加上一個 1 ，得到 cnt[5]=5，我們取最小值，得 cnt[5]=1。同理，i=6 分時，有 cnt[6] = cnt[6-5] + 1 = 2，對比原來的 cnt[6]=6，取最小值。繼續(xù)這個過程，結果是：
根據上述過程得到遞歸關系： cnt[i]=min(cnt[i],cnt[i?5]+1)
（3）繼續(xù)處理其它面值的硬幣
在 DP 中，把 cnt[i] 這樣的記錄子問題最優(yōu)解的數據稱為“狀態(tài)”；從 cnt[i?1] 或 cnt[i?5] 到 cnt[i] 的遞推，稱為“狀態(tài)轉移”。用前面子問題的結果，推導后續(xù)子問題的解，邏輯清晰、計算高效，這就是 DP 的特點。
這里我本人能力有限，找到一個c++版本的答案，大家看一看理解一下，之后會改成python1版本。
#include<bits/stdc++.h>using namespace std;const int M = 251; //定義最大金額const int N = 5; //5種硬幣int type[N] = {1, 5, 10, 25, 50}; //5種面值int cnt[M]; //每個金額對應最少的硬幣數量const int INF = 0x1FFFFFFF;void solve(){
for(int k = 0; k< M; k++) //初始值為無窮大
cnt[k] = INF;
cnt[0] = 0;
for(int j = 0; j < N; j++)
for(int i = type[j]; i < M; i++)
cnt[i] = min(cnt[i], cnt[i - type[j]] + 1); //遞推式}int main(){
int s;
solve(); //計算出所有金額對應的最少硬幣數量。打表
while(cin >> s){
if(cnt[s] == INF) cout <<"No answer" << endl;
else cout << cnt[s] << endl;
}
return 0;}題目數據讀入前就開始調用 solve() 函數，這是用到了“打表”的處理方法。即在輸入金額之前，提前用 solve() 算出所有的解，得到 cnt[M] 這個“表”，然后再讀取金額 s，查表直接輸出結果，查一次表的復雜度只有 O(1)。
這樣做的原因是，如果有很多組測試數據，例如 10000 個，那么總復雜度是O(N×M+10000)，沒有增加多少。如果不打表，每次讀一個 s，就用 solve() 算一次，那么總復雜度是 O(N×M×10000)，時間幾乎多了 1 萬倍。
但是現在只打印了最少硬幣數量，還沒打印出到底需要哪些面值的硬幣。
在 DP 中，除求最優(yōu)解的數量之外，往往還要求輸出最優(yōu)解本身，此時狀態(tài)表需要適當擴展，以包含更多信息。而在最少硬幣問題中，如果要求打印組合方案，需要增加一個記錄表 path[i]，記錄金額 i 需要的最后一個硬幣。再利用 path[] 逐步倒推，就能得到所有的硬幣。
舉個例子：金額 i=6,path[6]=5，表示最后一個硬幣是 5 分；然后，path[6-5] = path[1]，查path[1]=1，表示接下來的最后一個硬幣是 1 分；繼續(xù) path[1-1] = 0，不需要硬幣了，結束。輸出結果：硬幣組合是“5分 + 1分”。
這個也是c++版本，大家可以看一看理解大概。
#include<bits/stdc++.h>using namespace std;const int M = 251; //定義最大金額const int N = 5; //5種硬幣int type[N] = {1,5,10,25,50}; //5種面值int cnt[M]; //每個金額對應最少的硬幣數量int path[M]={0}; //記錄最小硬幣的路徑const int INF = 0x1FFFFFFF;void solve(){
for(int k=0; k< M;k++)
cnt[k] = INF;
cnt[0]=0;
for(int j = 0;j < N;j++)
for(int i = type[j]; i < M; i++)
if(cnt[i] > cnt[i - type[j]]+1){
path[i] = type[j]; //在每個金額上記錄路徑，即某個硬幣的面值
cnt[i] = cnt[i - type[j]] + 1; //遞推式
}}void print_ans(int *path, int s) { //打印硬幣組合
while(path[s]!=0 && s>0){
cout << path[s] << " ";
s = s - path[s];
}}int main() {
int s;
solve();
while(cin >> s){
if(cnt[s] == INF)
cout <<"No answer"<<endl;
else{
cout << cnt[s] << endl; //輸出最少硬幣個數
print_ans(path,s); //打印硬幣組合
}
}
return 0;}上面用 DP 解決了硬幣問題，看羅勇軍老師的博客，羅老師有以下總結：
兩個特征：重疊子問題、最優(yōu)子結構，就可以用 DP 高效率地處理、解決。
1.重疊子問題
首先，子問題是原大問題的小版本，計算步驟完全一樣；其次，計算大問題的時候，需要多次重復計算小問題。這就是“重疊子問題”。 一個子問題的多次計算，耗費了大量時間。用 DP 處理重疊子問題，每個子問題只需要計算一次，從而避免了重復計算，這就是 DP 效率高的原因。具體的做法是：首先分析得到最優(yōu)子結構，然后用遞推或者帶記憶化搜索的遞歸進行編程，從而實現了高效的計算。
2.最優(yōu)子結構
最優(yōu)子結構的意思是：首先，大問題的最優(yōu)解包含小問題的最優(yōu)解；其次，可以通過小問題的最優(yōu)解推導出大問題的最優(yōu)解。在硬幣問題中，我們把 cnt[i] 的計算，減小為cnt[i?1] 的計算，也就是把原來為i的大問題，減小為i?1的小問題，這是硬幣問題的最優(yōu)子結構。
解析來就是一道DP經典題背包問題
它是 DP 的經典問題。下面通過它來說下有關 DP 的：
狀態(tài)設計
狀態(tài)轉移方程
兩種編碼方法
滾動數組
題目描述
小明有一個容量為 V 的背包。
這天他去商場購物，商場一共有 N 件物品，第 i 件物品的體積為 wi，價值為vi。
小明想知道在購買的物品總體積不超過 V 的情況下所能獲得的最大價值為多少，請你幫他算算。
輸入描述
輸入第 1 行包含兩個正整數 N,V，表示商場物品的數量和小明的背包容量。
第 2～N+1 行包含 2 個正整數 w,v，表示物品的體積和價值。
1≤N≤102，1≤V≤103，1≤wi,vi≤103 。
輸出描述
輸出一行整數表示小明所能獲得的最大價值。
樣例輸入
5 20
1 6
2 5
3 8
5 15
3 3
樣例輸出
37
題目分析
我們得先設計好 DP 的狀態(tài)，才能進行 DP 的轉移等
那這題 DP 的狀態(tài)要如何設計呢？
對于這題，我們可以定義二維數組 dp[][]，大小為 N×C（dp[i][j] 表示把前 i 個物品（從第 1 個到第 i個）裝入容量為 j 的背包中獲得的最大價值）。我們把每個 dp[i][j] 都看成一個背包：背包容量為 j，裝 1～i 這些物品。最后得到的 dp[N][C] 就是問題的答案：把 N 個物品裝進容量 C 的背包的最大價值。
假設現在已經遞推計算到 dp[i][j] 了，那么我們考慮 2 種情況：
1.第 i 個物品的體積比容量 j 還大，不能裝進容量 j 的背包。那么直接繼承前i?1 個物品裝進容量 j 的背包的情況即可：dp[i][j]=dp[i?1][j]。
2.第 i 個物品的體積比容量 j 小，能裝進背包。此時又可以分為 2 種情況：裝或者不裝第 i個：
a.裝第 i 個。從前 i?1 個物品的情況下推廣而來，前i?1 個物品是 dp[i?1][j]。第 i 個物品裝進背包后，背包容量減少 c[i]，價值增加w[i]。所以有：dp[i][j] = dp[i-1][j-c[i]] + w[i]。
b.不裝第 i 個。那么：dp[i][j] = dp[i-1][j]。
我們取兩種情況的最大值，得狀態(tài)轉移方程是：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i])。
總結一下上述分析：背包問題的重疊子問題是 dp[i][j]，最優(yōu)子結構是 dp[i][j] 的狀態(tài)轉移方程。而對于算法的復雜度：算法需要計算二維矩陣 dp[][]，二維矩陣的大小是O(NC) 的，每一項計算時間是 O(1)，所以總時間復雜度是O(NC)，空間復雜度是 O(NC)。
舉個例子詳細說明一下:
假設現在有 4 個物品，其體積分別是 {2,3,6,5}，價值分別為{6,3,5,4}，背包的容量為 9。接下來考慮下填 dp[][] 表的過程，我們按照只裝第 1 個物品、只放前 2 個、只放前 3 個…的順序，一直到裝完，這就是從小問題擴展到大問題的過程。表格橫向 j，縱向 i，按先橫向遞增 j，再縱向遞增 i 的順序填表。
圖 dp 矩陣
我們分步來分析：
1.步驟 1：只裝第 1 個物品。由于物品 1 的體積是 2，所以背包容量小于 2 的，都放不進去，得
dp[1][0] = dp[1][1] = 0；而當物品 1 的體積等于背包容量時，能裝進去，背包價值就等于物品 1 的價值，得 dp[1][2] = 6；而對于容量大于 2 的背包，多余的容量用不到，所以價值和容量 2 的背包一樣。
圖 裝第1個物品
2.步驟 2：只裝前 2 個物品。如果物品 2 體積比背包容量大，那么不能裝物品 2，情況和只裝第 1 個一樣。見下圖中的 dp[2][0] = dp[2][1] = 0，dp[2][2] = 6。接著填 dp[2][3]。物品 2 體積等于背包容量，那么可以裝物品 2，也可以不裝：
（a）如果裝物品 2（體積是 3，價值也是 3），那么可以變成一個更小的問題，即只把物品 1 裝到（容量j?3）的背包中。
圖 裝第2個物品
（b）如果不裝物品 2，那么相當于只把物品 1 裝到背包中。
圖 完成dp矩陣
最后的答案是dp[4][9] ：把 4 個物品裝到容量為 9 的背包，最大價值是 11。
上面表格中的數字是背包的最大價值，那么如何輸出背包方案呢？
要想知道具體裝了哪些物品，需要倒過來觀察：
dp[4][9]=max(dp[3][4]+4,dp[3][9])=dp[3][9]，說明沒有裝物品 4，用 x4=0 表示；
dp[3][9]=max(dp[2][3]+5,dp[2][9])=dp[2][3]+5=11，說明裝了物品 3，x3=1；
dp[2][3]=max(dp[1][0]+3,dp[1][3])=dp[1][3]，說明沒有裝物品 2，x2 =0；
dp[1][3]=max(dp[0][1]+6,dp[0][3])=dp[0][1]+6=6，說明裝了物品 1，x1=1。
下圖中的實線箭頭標識了方案的轉移路徑。
記憶化代碼和遞推代碼
接下來說說動態(tài)規(guī)劃最重要的代碼實現部分（有兩種實現方法）。處理 DP 中的大問題和小問題，有兩種思路：自頂向下（Top-Down，先大問題再小問題）、自下而上（Bottom-Up，先小問題再大問題）。而在編碼實現 DP 時，自頂向下用帶記憶化搜索的遞歸編碼，自下而上用遞推編碼。
兩種方法的復雜度是一樣的，每個子問題都計算一遍，而且只計算一遍。下面我們分別實現自下而上的遞推和自上而下的記憶化遞歸實現。
自下而上
遞推代碼 - Python
這種“自下而上”的方法，先解決子問題，再遞推到大問題。通常填寫多維表格來完成，編碼時用若干 for循環(huán)語句填表。根據表中的結果，逐步計算出大問題的解決方案。這就是上面詳解中的遞推式的直接實現。
N=3011dp = [[0 for i in range(N)] for j in range(N)]w = [0 for i in range(N)]c = [0 for i in range(N)]def solve(n,C): for i in range(1,n+1): for j in range (0,C+1): if c[i]>j : dp[i][j] = dp[i-1][j] else : dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i]) return dp[n][C] n, C = map(int, input().split())for i in range(1, n+1): c[i], w[i] = map(int, input().split())print(solve(n, C))
自上而下
記憶化代碼 - Python
N=3011dp = [[0 for i in range(N)] for j in range(N)]w = [0 for i in range(N)]c = [0 for i in range(N)]def solve(n,C): for i in range(1,n+1): for j in range (0,C+1): if c[i]>j : dp[i][j] = dp[i-1][j] else : dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i]) return dp[n][C] n, C = map(int, input().split())for i in range(1, n+1): c[i], w[i] = map(int, input().split())print(solve(n, C))
滾動數組
DP 的狀態(tài)方程常常是二維和二維以上，占用了太多的空間。例如前面代碼使用了二維矩陣 int dp[N][C]，設 N = 103，C = 104，都不算大。但 int 型有 4 字節(jié)，需要的空間是 4×103×104 = 40M，會超過部分競賽題的空間限制。
不過我們可以用滾動數組大大減少空間。它能把二維狀態(tài)方程的 O(n2) 空間復雜度，優(yōu)化到 O(n)，更高維的數組也可以優(yōu)化后減少一維。
這個叫滾動數組的玩意兒是如何優(yōu)化的？
從狀態(tài)轉移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j - c[i]] + w[i]) 可以看出，dp[i][] 只和dp[i?1][] 有關，和前面的 dp[i?2][]、dp[i?3][]、? 都沒有關系。從前面的圖表也可以看出，每一行是從上面一行算出來的，跟更前面的行沒有關系。而那些用過的已經無用的 dp[i?2][]、dp[i?3][]、? 多余了，那么干脆就復用這些空間，用新的一行覆蓋已經無用的一行（滾動），這樣只需要兩行就夠了。
下面給出滾動數組的兩種實現方法，兩種實現都很常用：
交替滾動
定義 dp[2][j]，用 dp[0][] 和 dp[1][] 交替滾動。這種方法的優(yōu)點是邏輯清晰、編碼不易出錯，建議作為初學者的你采用這個方法。
交替滾動 - Python
N = 3011dp = [[0 for i in range(N)] for j in range(2)] #注意先后w = [0 for i in range(N)]c = [0 for i in range(N)]def solve(n,C): now = 0 old =1 for i in range(1,n+1): old,now = now,old #交換 for j in range (0,C+1,1): if c[i] > j: dp[now][j]=dp[old][j] else: dp[now][j] = max(dp[old][j], dp[old][j-c[i]]+w[i]) return dp[now][C] n, C = map(int, input().split())for i in range(1, n+1): c[i], w[i] = map(int, input().split())print(solve(n, C))
自我滾動
用兩行交替滾動是很符合邏輯的做法，其實還能繼續(xù)精簡：用一個一維的dp[] 就夠了，自己滾動自己。
自我滾動 - Python
N=3011dp = [0 for i in range(N)]w = [0 for i in range(N)]c = [0 for i in range(N)]def solve(n,C): for i in range(1,n+1): for j in range (C,c[i]-1,-1): dp[j] = max(dp[j], dp[j-c[i]]+w[i]) return dp[C] n, C = map(int, input().split())for i in range(1, n+1): c[i], w[i] = map(int, input().split())print(solve(n, C))
文章來源：http://www.zghlxwxcb.cn/news/detail-400156.html
不過滾動數組也有缺點。它覆蓋了中間轉移狀態(tài)，只留下了最后的狀態(tài)，損失了很多信息，無法回溯，導致不能輸出具體的方案。不過，競賽題目一般不要求輸出具體方案，因為可能有多種方案，不方便判題。
以上就是動態(tài)規(guī)劃的基本內容了。文章來源地址http://www.zghlxwxcb.cn/news/detail-400156.html
到了這里，關于DP算法應用：背包問題解析與實現的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
