四月份還沒寫，不能這么荒廢了呀，趕緊水一篇吧，哈哈。前些日子回顧了DP的一些基礎(chǔ)，就做一下整理吧，從0-1背包開始。
本節(jié)回顧0-1背包的基本模型，關(guān)于它的實現(xiàn)有很多種寫法，這里對不同實現(xiàn)做個簡單列舉，主要是寫代碼練手了，主要有以下幾方面內(nèi)容：
==0-1背包問題定義 & 基本實現(xiàn)
==0-1背包使用滾動數(shù)組壓縮空間
==0-1背包使用一維數(shù)組
==0-1背包恰好背滿
==0-1背包輸出最優(yōu)方案
========================================
0-1背包問題定義 & 基本實現(xiàn)
問題：有個容量為V大小的背包，有很多不同重量weight[i](i=1..n)不同價值value[i](i=1..n)的物品，每種物品只有一個，想計算一下最多能放多少價值的貨物。
DP的關(guān)鍵也是難點是找到最優(yōu)子結(jié)構(gòu)和重疊子問題，進而找到狀態(tài)轉(zhuǎn)移方程，編碼就相對容易些。最優(yōu)子結(jié)構(gòu)保證每個狀態(tài)是最優(yōu)的，重疊子問題也即n狀態(tài)的求法和n-1狀態(tài)的求法是一樣的；DP在實現(xiàn)上一般是根據(jù)狀態(tài)轉(zhuǎn)移方程自底向上的迭代求得最優(yōu)解（也可以使用遞歸自頂向下求解）。
回到0-1背包，每個物體i，對應(yīng)著兩種狀態(tài)：放入&不放入背包。背包的最優(yōu)解是在面對每個物體時選擇能夠最大化背包價值的狀態(tài)。0-1背包的狀態(tài)轉(zhuǎn)移方程為
|
1
|
f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] } |
f(i,v)表示前i個物體面對容量為v時背包的最大價值，c[i]代表物體i的cost(即重量)，w[i]代表物體i的價值；如果第i個物體不放入背包，則背包的最大價值等于前i-1個物體面對容量v的最大價值；如果第i個物體選擇放入，則背包的最大價值等于前i-1個物體面對容量v-cost[i]的最大價值加上物體i的價值w[i]。
對于實現(xiàn)，一般采用一個二維數(shù)組（狀態(tài)轉(zhuǎn)移矩陣）dp[i][j]來記錄各個子問題的最優(yōu)狀態(tài)，其中dp[i][j]表示前i個物體面對容量j背包的最大價值。
下面給出0-1背包的基本實現(xiàn)，時間復(fù)雜度為O(N*V)，空間復(fù)雜度也為O(N*V)，初始化的合法狀態(tài)很重要，對于第一個物體即f[0][j]，如果容量j小于第一個物體（編號為0）的重量，則背包的最大價值為0，如果容量j大于第一個物體的重量，則背包最大價值便為該物體的價值。為了能單步驗證每個狀態(tài)的最優(yōu)解，程序最后將狀態(tài)轉(zhuǎn)移矩陣的有效部分輸出到了文件。
代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <iostream>using namespace std;/* 0-1背包 版本1 * Time Complexity O(N*V) * Space Complexity O(N*V) * 設(shè) V <= 200 N <= 10 * 狀態(tài)轉(zhuǎn)移方程：f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] } */int maxValue[11][201]; /* 前i個物體面對容量j的最大價值，即子問題最優(yōu)解 */int weight[11];int value[11];int V, N;void main(){ int i, j; scanf("%d %d",&V, &N); for(i = 0; i < N; ++i) { scanf("%d %d",&weight[i],&value[i]); } for(i = 0; i < N; ++i) { for(j = 0; j <= V; ++j) /* 容量為V 等號 */ { if(i > 0) { maxValue[i][j] = maxValue[i-1][j]; if(j >= weight[i]) /* 等號 */ { int tmp = maxValue[i-1][j-weight[i]] + value[i]; maxValue[i][j] = ( tmp > maxValue[i][j]) ? tmp : maxValue[i][j]; } }else /* 數(shù)組第0行賦值 */ { if(j >= weight[0]) maxValue[0][j] = value[0]; } } } printf("%d",maxValue[N-1][V]); /* 重定向輸出結(jié)果到文件 */ freopen("C:\\dp.txt","w",stdout); for(i = 0; i <= N; ++i) { for(j = 0; j <= V; ++j) { printf("%d ",maxValue[i][j]); } printf("\n"); }} |
測試用例：
|
1
2
3
4
5
6
7
|
10 33 44 65 7 |
程序輸出的狀態(tài)轉(zhuǎn)移矩陣如下圖，第一行表示第1個物體對于容量0至V時的最優(yōu)解，即背包最大價值。該實現(xiàn)方法是0-1背包最基本的思想，追蹤狀態(tài)轉(zhuǎn)移矩陣有助于加深理解，POJ上單純的0-1背包題目也有不少，如3624等，可以水一下，加深理解。
========================================
0-1背包使用滾動數(shù)組壓縮空間
所謂滾動數(shù)組，目的在于優(yōu)化空間，從上面的解法我們可以看到，狀態(tài)轉(zhuǎn)移矩陣使用的是一個N*V的數(shù)組，在求解的過程中，我們可以發(fā)現(xiàn)，當(dāng)前狀態(tài)只與前一狀態(tài)的解有關(guān)，那么之前存儲的狀態(tài)信息已經(jīng)無用了，可以舍棄的，我們只需要空間存儲當(dāng)前的狀態(tài)和前一狀態(tài)，所以只需使用2*V的空間，循環(huán)滾動使用，就可以達到跟N*V一樣的效果。這是一個非常大的空間優(yōu)化。
代碼如下，我們可以在每輪內(nèi)循環(huán)結(jié)束后輸出當(dāng)前狀態(tài)的解，與上面使用二維數(shù)組輸出的狀態(tài)轉(zhuǎn)移矩陣對比，會發(fā)現(xiàn)是一樣的效果，重定向輸出到文本有助加深理解。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <iostream>using namespace std;/* 0-1背包 版本2 * Time Complexity O(N*V) * Space Complexity O(2*V) * 設(shè) V <= 200 N <= 10 * 狀態(tài)轉(zhuǎn)移方程：f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] } */int maxValue[2][201]; /* 前i個物體面對容量j的最大價值，即子問題最優(yōu)解 */int weight[11];int value[11];int V, N;void main(){ int i, j, k; scanf("%d %d",&V, &N); for(i = 0; i < N; ++i) { scanf("%d %d",&weight[i],&value[i]); } for(i = 0; i < N; ++i) { for(j = 0; j <= V; ++j) /* 容量為V 等號 */ { if(i > 0) { k = i & 1; /* i%2 獲得滾動數(shù)組當(dāng)前索引 k */ maxValue[k][j] = maxValue[k^1][j]; if(j >= weight[i]) /* 等號 */ { int tmp = maxValue[k^1][j-weight[i]] + value[i]; maxValue[k][j] = ( tmp > maxValue[k][j]) ? tmp : maxValue[k][j]; } }else /* 數(shù)組第0行賦值 */ { if(j >= weight[0]) maxValue[0][j] = value[0]; } } } printf("%d",maxValue[k][V]); /* 重定向輸出結(jié)果到文件 */ freopen("C:\\dp.txt","w",stdout); for(i = 0; i <= 1; ++i) { for(j = 0; j <= V; ++j) { printf("%d ",maxValue[i][j]); } printf("\n"); }} |
這種空間循環(huán)滾動使用的思想很有意思，類似的，大家熟悉的斐波那契數(shù)列，f(n) = f(n-1) + f(n-2)，如果要求解f(1000)，是不需要申請1000個大小的數(shù)組的，使用滾動數(shù)組只需申請3個空間f[3]就可以完成任務(wù)。
========================================
0-1背包使用一維數(shù)組
使用滾動數(shù)組將空間優(yōu)化到了2*V，在背包九講中提到了使用一維數(shù)組也可以達到同樣的效果，個人認為這也是滾動思想的一種，由于使用一維數(shù)組解01背包會被多次用到，完全背包的一種優(yōu)化實現(xiàn)方式也是使用一維數(shù)組，所以我們有必要理解這種方法。
如果只使用一維數(shù)組f[0…v]，我們要達到的效果是：第i次循環(huán)結(jié)束后f[v]中所表示的就是使用二維數(shù)組時的f[i][v]，即前i個物體面對容量v時的最大價值。我們知道f[v]是由兩個狀態(tài)得來的，f[i-1][v]和f[i-1][v-c[i]]，使用一維數(shù)組時，當(dāng)?shù)趇次循環(huán)之前時，f[v]實際上就是f[i-1][v]，那么怎么得到第二個子問題的值呢？事實上，如果在每次循環(huán)中我們以v=v…0的順序推f[v]時，就能保證f[v-c[i]]存儲的是f[i-1][v-c[i]]的狀態(tài)。狀態(tài)轉(zhuǎn)移方程為：
|
1
|
v = V...0; f(v) = max{ f(v), f(v-c[i])+w[i] } |
我們可以與二維數(shù)組的狀態(tài)轉(zhuǎn)移方程對比一下
|
1
|
f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] } |
正如我們上面所說，f[v-c[i]]就相當(dāng)于原來f[i-1][v-c[i]]的狀態(tài)。如果將v的循環(huán)順序由逆序改為順序的話，就不是01背包了，就變成完全背包了，這個后面說。這里舉一個例子理解為何順序就不是01背包了
假設(shè)有物體z容量2，價值vz很大，背包容量為5，如果v的循環(huán)順序不是逆序，那么外層循環(huán)跑到物體z時，內(nèi)循環(huán)在v=2時，物體z被放入背包，當(dāng)v=4時，尋求最大價值，物體z放入背包，f[4]=max{f[4],f[2]+vz}，這里毫無疑問后者最大，那么此時f[2]+vz中的f[2]已經(jīng)裝入了一次物體z，這樣一來該物體被裝入背包兩次了就，不符合要求，如果逆序循環(huán)v，這一問題便解決了。
代碼如下，為了加深理解，可以在內(nèi)循環(huán)結(jié)束輸出每一個狀態(tài)的情況到文本中，會發(fā)現(xiàn)與使用二維數(shù)組時的狀態(tài)轉(zhuǎn)移矩陣都是一樣一樣的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <iostream>using namespace std;/* 0-1背包 版本3 * Time Complexity O(N*V) * Space Complexity O(V) * 設(shè) V <= 200 N <= 10 * 狀態(tài)轉(zhuǎn)移方程：v = V...0; f(v) = max{ f(v), f(v-c[i])+w[i] } */int maxV[201]; /* 記錄前i個物品中容量v時的最大價值 */int weight[11];int value[11];int V, N;void main(){ int i, j; scanf("%d %d",&V, &N); for(i = 0; i < N; ++i) { scanf("%d %d",&weight[i],&value[i]); } /* * 對于第i輪循環(huán) * 求出了前i個物品中面對容量為v的最大價值 */ for(i = 0; i < N; ++i) { /* * 內(nèi)循環(huán)實際上講maxV[0...v]滾動覆蓋前一輪的maxV[0...V] * 可輸出對照使用二維數(shù)組時的情況 * j從V至0逆序是防止有的物品放入背包多次 */ for(j = V; j >= weight[i]; --j) /* weight > j 的物品不會影響狀態(tài)f[0,weight[i-1]] */ { int tmp = maxV[j-weight[i]]+value[i]; maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp; } } printf("%d",maxV[V]);} |
可以看出，使用一維數(shù)組，代碼非常簡練。
========================================
0-1背包恰好背滿
在01背包中，有時問到“恰好裝滿背包”時的最大價值，與不要求裝滿背包的區(qū)別就是在初始化的時候，其實對于沒有要求必須裝滿背包的情況下，初始化最大價值都為0，是不存在非法狀態(tài)的，所有的都是合法狀態(tài)，因為可以什么都不裝，這個解就是0，但是如果要求恰好裝滿，則必須區(qū)別初始化，除了f[0]=0,其他的f[1…v]均設(shè)為-∞或者一個比較大的負數(shù)來表示該狀態(tài)是非法的。
這樣的初始化能夠保證，如果子問題的狀態(tài)是合法的（恰好裝滿），那么才能得到合法的狀態(tài)；如果子問題狀態(tài)是非法的，則當(dāng)前問題的狀態(tài)依然非法，即不存在恰好裝滿的情況。
代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <iostream>using namespace std;int maxV[201]; /* 記錄前i個物品中容量v時的最大價值 */int weight[11];int value[11];int V, N;void main(){ int i, j; scanf("%d %d",&V, &N); for(i = 0; i < N; ++i) { scanf("%d %d",&weight[i],&value[i]); } for(i = 1; i <= V; ++i) /* 初始化非法狀態(tài) */ { maxV[i] = -100; } for(i = 0; i < N; ++i) { for(j = V; j >= weight[i]; --j) { int tmp = maxV[j-weight[i]]+value[i]; maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp; } }} |
為了加深理解，輸出每輪循環(huán)的狀態(tài)矩陣如下，對照每個物體的情況，就會理解為什么做那樣的初始化了。
========================================
0-1背包輸出最優(yōu)方案
一般來講，背包問題都是求一個最優(yōu)值，但是如果要求輸出得到這個最優(yōu)值的方案，就可以根據(jù)狀態(tài)轉(zhuǎn)移方程往后推，由這一狀態(tài)找到上一狀態(tài)，依次向前推即可。
這樣就可以有兩種實現(xiàn)方式，一種是直接根據(jù)狀態(tài)轉(zhuǎn)移矩陣向前推，另一種就是使用額外一個狀態(tài)矩陣記錄最優(yōu)方案的路徑，道理都是一樣的。當(dāng)然也可以使用一維數(shù)組，代碼更為簡練，這里不羅列，相關(guān)代碼可以到這里下載。
代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <iostream>using namespace std;/* 0-1背包 輸出最優(yōu)方案 2 直接根據(jù)狀態(tài)數(shù)組算 * Time Complexity O(N*V) * Space Complexity O(N*V) * 設(shè) V <= 200 N <= 10 * 狀態(tài)轉(zhuǎn)移方程：f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] } */int maxValue[11][201]; /* 記錄子問題最優(yōu)解 */int weight[11];int value[11];int V, N;void main(){ int i, j; scanf("%d %d",&V, &N); for(i = 0; i < N; ++i) { scanf("%d %d",&weight[i],&value[i]); } for(i = 0; i < N; ++i) { for(j = 0; j <= V; ++j) { if(i > 0) { maxValue[i][j] = maxValue[i-1][j]; if(j >= weight[i]) { int tmp = maxValue[i-1][j-weight[i]] + value[i]; maxValue[i][j] = ( tmp > maxValue[i][j]) ? tmp : maxValue[i][j]; } }else { if(j >= weight[0]) maxValue[0][j] = value[0]; } } } printf("%d\n",maxValue[N-1][V]); i = N-1; j = V; while(i >= 0) { if(maxValue[i][j] == maxValue[i-1][j-weight[i]] + value[i]) { printf("%d ",i); j = j - weight[i]; } --i; }} |
01背包是背包問題的基礎(chǔ)，加深理解的最好方式就是動手寫一下，然后對照最終的狀態(tài)轉(zhuǎn)移矩陣一一比對。
本
