題目
給定一組物品扩灯，每種物品都有自己的重量和價格媚赖，在限定的總重量內(nèi)，我們?nèi)绾芜x擇珠插，才能使得物品的總價格最高惧磺。
0 - 1 背包問題背后的圖
0-1背包.png
解法思路（一）記憶化遞歸
問題狀態(tài)的定義
-
F(n, C)考慮將 n 個物品，放進容量為 C 的背包捻撑，是價值最大磨隘；
價值最大的兩種情況
- 第
n - 1個元素不放進背包中，背包中的價值最大顾患，對應的狀態(tài)為：F(n-2, C)番捂； - 第
n - 1個元素放進背包中，背包中的價值最大江解，對應的狀態(tài)為：v[n-1] + F(n-2, C-w[n-1]设预；
哪種情況的價值最大？
max( F(n-2, C), v[n-1] + F(n-2, C-w[n-1]) )
解法實現(xiàn)（一）記憶化遞歸
實現(xiàn)細節(jié)
- 記憶數(shù)組
memo是二維的犁河；
package knapsack;
public class Solution1 {
private int[][] memo;
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
memo = new int[n][C + 1];
return bestValue(w, v, n - 1, C);
}
// 用 [0...index] 的物品,填充容積為c 的背包的最大價值
private int bestValue(int[] w, int[] v, int index, int c){
if(c <= 0 || index < 0)
return 0;
if(memo[index][c] != -1)
return memo[index][c];
int res = bestValue(w, v, index-1, c);
if(c >= w[index])
res = Math.max(res,
v[index] + bestValue(w, v, index - 1, c - w[index]));
return memo[index][c] = res;
}
}
解法思路（二）動態(tài)規(guī)劃
思路描述
- 把頭 1 個元素放進背包中鳖枕，最大價值就是數(shù)組中
memo[0][C]； - 把頭 2 個元素放進背包中桨螺，最大價值就是數(shù)組中
memo[1][C]宾符； - ...
- 把頭 n 個元素放進背包中，最大價值就是數(shù)組中
memo[n - 1][C]灭翔；
memo 數(shù)組怎么填吸奴？
- 從左上角到右下角一行一行一格一格的填；
- 第一行的填法是：容量比
w[0]小的的格都填 0缠局，其余都填v[0]； - 第二行開始的填法：
- 容量比
w[i]小的格考润，把頭頂上那格memo[i-1][j]的值落下來狭园； - 容量大于等于
w[i]的格，比較memo[i-1][j]和v[i] + memo[i - 1][j - w[i]]的值的大泻巍唱矛；
- 容量比
解法實現(xiàn)（二）動態(tài)規(guī)劃
實現(xiàn)細節(jié)
- 從數(shù)組
memo的左上開始填，一直填到右下，右下角的值就是背包問題的題解绎谦；
package knapsack;
public class Solution2 {
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
int[][] memo = new int[n][C + 1];
for(int j = 0 ; j <= C ; j ++)
memo[0][j] = (j >= w[0] ? v[0] : 0 );
for(int i = 1 ; i < n ; i ++)
for(int j = 0 ; j <= C ; j ++){
memo[i][j] = memo[i-1][j];
if(j >= w[i])
memo[i][j] = Math.max(memo[i][j], v[i] + memo[i - 1][j - w[i]]);
}
return memo[n - 1][C];
}
}
解法實現(xiàn)（三）動態(tài)規(guī)劃 優(yōu)化
優(yōu)化結果
- 空間復雜度從
n * C變成2 * C管闷；
package knapsack;
public class Solution3 {
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
int[][] memo = new int[2][C + 1];
for(int j = 0 ; j <= C ; j ++)
memo[0][j] = (j >= w[0] ? v[0] : 0);
for(int i = 1 ; i < n ; i ++)
for(int j = 0 ; j <= C ; j ++){
memo[i % 2][j] = memo[(i-1) % 2][j];
if(j >= w[i])
memo[i % 2][j] = Math.max(memo[i % 2][j], v[i] + memo[(i-1) % 2][j - w[i]]);
}
return memo[(n-1) % 2][C];
}
}
解法實現(xiàn)（四）動態(tài)規(guī)劃 優(yōu)化
優(yōu)化結果
- 空間復雜度從
2 * C變成C；
package knapsack;
public class Solution4 {
public int knapsack01(int[] w, int[] v, int C){
if(w == null || v == null || w.length != v.length)
throw new IllegalArgumentException("Invalid w or v");
if(C < 0)
throw new IllegalArgumentException("C must be greater or equal to zero.");
int n = w.length;
if(n == 0 || C == 0)
return 0;
int[] memo = new int[C+1];
for(int j = 0 ; j <= C ; j ++)
memo[j] = (j >= w[0] ? v[0] : 0);
for(int i = 1 ; i < n ; i ++)
for(int j = C ; j >= w[i] ; j --)
memo[j] = Math.max(memo[j], v[i] + memo[j - w[i]]);
return memo[C];
}
}
