最近學(xué)習(xí)《背包問題九講》,對(duì)0-1背包和完全背包有了新的認(rèn)識(shí)矾克。最新版本請(qǐng)?jiān)L問 https://github.com/tianyicui/pack 查閱。
1.01背包問題
關(guān)于01背包問題的方程式如下续镇，此時(shí)的時(shí)間復(fù)雜度位O(NV)，N為狀態(tài)數(shù)目收毫，V為背包總大小闸昨，空間復(fù)雜度位O(NV)：
F [i, v] = max {F [i ? 1, v], F [i ? 1, v ? C i ] + W i }
通過復(fù)用DP矩陣，可以將之轉(zhuǎn)換為O(V)况鸣，V為背包大小牢贸，此時(shí)的偽代碼為：
F [0..V ] ←0
for i ← 1 to N
for v ← V to C i
F [v] ← max {F [v], F [v ? C i ] + W i }
2.完全背包
這個(gè)問題非常類似于01背包問題,所不同的是每種物品有無限件。也就
是從每種物品的角度考慮,與它相關(guān)的策略已并非取或不取兩種,而是有
取 0 件镐捧、取 1 件潜索、取 2 件......直至取 ?V /C i ? 件等許多種。
如果仍然按照解01背包時(shí)的思路,令 F [i, v] 表示前 i 種物品恰放入一個(gè)容
量為 v 的背包的最大權(quán)值懂酱。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程,像這樣:
F [i, v] = max (F [i ? 1, v], F [i, v ? C i ] + W i )
其O(V)的偽代碼如下：
F [0..V ] ←0
for i ← 1 to N
for v ← C i to V
F [v] ← max (F [v], F [v ? C i ] + W i )
3.背包問題應(yīng)用
第一節(jié)已經(jīng)給出了01背包在O(V)條件下的偽代碼竹习，這里給出其O(NV)狀態(tài)下的偽代碼：
F [0, 0..V ] ← 0
for i ← 1 to N
for v ← C i to V
F [i, v] ← max {F [i ? 1, v], F [i ? 1, v ? C i ] + W i }
上面可以看到，從i-1狀態(tài)下變遷過來的狀態(tài)之間是隔離的列牺，每個(gè)i狀態(tài)和i-1狀態(tài)相關(guān)整陌。
而完全背包則不是這樣，按照F [i, v] = max {F [i ? 1, v ? kC i ] + kW i | 0 ≤ kC i ≤ v}的轉(zhuǎn)移方程獲得如下代碼：
F[0][] ← {0}
F[][0] ← {0}
for i←1 to N
do for j←1 to V
do for k←0 to j/C[i]
if(j >= k*C[i])
then F[i][k] ← max(F[i][k],F[i-1][j-k*C[i]]+k*W[i])
return F[N][V]
如此情況下的時(shí)間復(fù)雜度為O(NV∑(j/C[i]))瞎领。要獲得O(VN)時(shí)間復(fù)雜度的完全背包解法泌辫，需要用到第二節(jié)使用的遞推關(guān)系式，其偽代碼第二節(jié)也已經(jīng)介紹了九默。
這里我使用LeetCode上343. Integer Break 來講解震放。
第一種，不服用DP矩陣驼修。
public int integerBreak(int n) {
if (n <= 1) return 0;
int[][] dp = new int[n + 1][n + 1];
dp[0][1] =1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (j < i) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j],
Math.max(dp[i][j - i], j - i) *
Math.max(dp[i][i], i));
}
}
}
return dp[n][n];
}
第二種殿遂，復(fù)用DP矩陣。
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for(int i = 2; i <= n; i ++) {
for(int j = 1; j < i; j ++) {
dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
}
}
return dp[n];
}
4.總結(jié)
（Tips：O(NV)時(shí)間復(fù)雜度）
× 01背包的狀態(tài)遷移是前后無關(guān)的乙各，i狀態(tài)由i-1狀態(tài)遷移而來墨礁，因此，必須保證前狀態(tài)的狀態(tài)無法影響后狀態(tài)耳峦。因此饵溅，在O(V)空間復(fù)雜度下，必須從后往前遷移狀態(tài)妇萄，防止?fàn)顟B(tài)疊加。
× 完全背包的狀態(tài)是需要疊加的咬荷。因此在O(NV)空間復(fù)雜度狀態(tài)下的狀態(tài)遷移冠句，需要收到i狀態(tài)下其他背包的影響。O(V)空間復(fù)雜度下幸乒，則從前向后推移狀態(tài)懦底。
