文章目錄
- 怎麼初始化？(重要)
- 0-1背包
-
- 解題範式
- 代碼模闆
- 狀态壓縮優化(最大)
- 0-1背包練習
- 完全背包
-
- 完全背包練習
- 01和完全總結
- 多重背包
-
- 基礎代碼
- 空間優化
- 與01背包的關系
- 二進制優化時間
怎麼初始化？(重要)
求最優解的背包問題題目中，有的題目要求“
恰好裝滿背包”
時的最優解，有的題目則并沒有要求必須把背包裝滿。二者差別在于
初始化的時候有所不同
。
- 求恰好裝滿背包，那麼初始化
dp[0]=0，dp[1..V]=-∞
dp[N]
- 如果并沒有要求必須把背包裝滿，而是隻希望結果盡量大，初始化時應該将
dp[0..V]全部設為0
解釋：
如果恰好裝滿背包，初始化的dp數組就是在沒有任何物品可以放入背包時的
合法狀态
。如果要求背包恰好裝滿，那麼此時隻有容量為0的背包可能被價值為0的nothing
“恰好裝滿”
，其它容量的背包均沒有合法的解，屬于未定義的狀态，它們的值就都應該是
-∞
了。
如果背包并非必須被裝滿，那麼任何容量的背包都有一個合法解就是
“什麼都不裝”
，這個解的價值為0，是以初始時狀态的值也就全部為0了。
0-1背包
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使價值總和最大。
解題範式
1、明确狀态，狀态有兩個，就是「背包的容量」和「可選擇的物品」。
2、明确選擇，選擇就是「裝進背包」或者「不裝進背包」。
3、 要明确
dp
數組的定義
「狀态」有兩個，是以定義二維
dp
數組，一維表示可選擇的物品，一維表示背包的容量。
dp[i][w]
：對于前
i
個物品，目前背包的容量為
w
，這種情況下可以裝的
最大價值
是
dp[i][w]
根據這個定義，我們想求的最終答案就是
dp[N][W]
。
4、由選擇确定狀态轉移方程
dp[i][w] = max(
dp[i-1][w], //不裝第i件物品
dp[i-1][w - wt[i-1]] + val[i-1] //裝第i件物品
)
5、base case
沒有物品或者背包沒有空間的時候，能裝的最大價值就是 0。是以
dp[0][..] = dp[..][0] = 0
代碼模闆
class Solution {
/*
W:背包總容量
N:物品總個數
wt:物品重量
val；物品價值
*/
int knapsack ( int W, int N, int wt[], int val[]){
int[][] dp=new int[N+1][W+1];
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (w < wt[i - 1]) {
// 目前背包容量裝不下，隻能選擇不裝入背包
dp[i][w] = dp[i - 1][w];
} else {
// 裝得下，擇優選擇裝入或者不裝入
dp[i][w] = Math.max(dp[i - 1][w - wt[i - 1]] + val[i - 1], dp[i - 1][w]);
}
}
}
return dp[N][W];
}
}
狀态壓縮優化(最大)
為什麼對容量的周遊必須改為逆序？
因為現在隻有一維，算第i行時會把i-1行覆寫掉，當算一個位置的值時需要的是它左上角的上一行的結果，順序周遊的話左上角在之前就被覆寫了，逆序的話覆寫的是右上角，而右上角被覆寫之後不需要被用到，是以被覆寫也沒事。是以必須逆序！
class Solution {
int knapsack ( int W, int N, int wt[], int val[]){
int[]dp=new int[W+1];
for (int i = 1; i <= N; i++) {
for (int w = W; w>=wt[i-1]; w--) { //注意w>=wt[i]，小于w的容量就不用考慮了，但是二維解法中必須考慮
dp[w]=Math.max(dp[w-wt[i-1]]+val[i-1],dp[w]);
}
}
return dp[W];
}
}
0-1背包練習
完全背包
有N種物品和一個容量為V的背包，每種物品都有
無限件可用
。第i種物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
分析完全背包的解法
為什麼必須正序周遊v？
完全背包練習
01和完全總結
01
标準做法：
狀态壓縮做法
完全與01的差別
标準做法：
狀态壓縮做法
多重背包
有n種物品和一個容量為 capacity 的背包，每種物品
「數量有限」
。
第 i 件物品的體積是 volume[i]，價值是val[i] ，數量為 num[i]。
問選擇哪些物品，每件物品選擇多少件，可使得總價值最大。
其實就是在 0-1 背包問題的基礎上，增加了每件物品可以選擇
「有限次數」
的特點（在容量允許的情況下）。
狀态轉移方程：
基礎代碼
class Solution {
public int maxValue(int capacity, int[] val, int[] volume, int[] num) {
int n=num.length; //商品數量
int[][]dp=new int[n+1][capacity+1];
for (int i=1;i<=n;i++){
for(int j=1;j<=capacity;j++){
for (int k=0;k<=num[i];k++){
if(k*volume[i-1]>j){
dp[i][j]=dp[i-1][j];
}else {
dp[i][j]=Math.max(dp[i][j],dp[i-1][j-k*volume[i-1]]+k*val[i-1]);
}
}
}
}
return dp[n][capacity];
}
}
空間優化
class Solution {
public int maxValue(int capacity, int[] val, int[] volume, int[] num) {
int[]dp=new int[capacity+1];
for (int i=1;i<=n;i++){
for(int j=capacity;j>=volume[i];j--){ //逆序！
for (int k=0;k<=num[i] && k*volume[i]<=j;k++){
dp[j]=Math.max(dp[j],dp[j-k*volume[i-1]]+k*val[i-1]);
}
}
}
return dp[capacity];
}
}
與01背包的關系
可以将「多重背包」看做是一種特殊的「01 背包」。
對「01 背包」中
具有相同的價值與成本的物品
進行計數，就成了對應物品的「限制件數」，「01 背包」也就轉換成了「多重背包」。
同理，将「多重背包」的多件物品進行「扁平化展開」，就轉換成了「01 背包」。
多重轉01代碼
class Solution {
public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
// 将多件數量的同一物品進行「扁平化」展開，以 [v, w] 形式存儲
List<int[]> arr = new ArrayList<>();
for (int i = 0; i < N; i++) {
int cnt = s[i];
while (cnt-- > 0) {
arr.add(new int[]{v[i], w[i]});
}
}
// 使用「01 背包」進行求解
int[] dp = new int[C + 1];
for (int i = 0; i < arr.size(); i++) {
int vi = arr.get(i)[0], wi = arr.get(i)[1];
for (int j = C; j >= vi; j--) {
dp[j] = Math.max(dp[j], dp[j - vi] + wi);
}
}
return dp[C];
}
}
轉換成「01 背包」之後。效率上還要稍微差一點，因為額外增大了“常數”。
我們來可以分析一下為什麼。
首先，扁平化操作并沒有使得物品“變少”，我們仍然需要枚舉所有的“組合”，從中選擇最優，組合的數量沒有發生變化，還額外增加了扁平化的操作。
直接的轉換并不能帶來效率上的提升，但是可以讓我們更加了解兩者之間的關系。
二進制優化時間
上面的三種寫法的時間複雜度都是 O(n^3)
這意味着我們隻能解決 10^2 數量級的「多重背包」問題。
下面二進制優化時間代碼：
class Solution {
public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
// 扁平化
List<Integer> worth = new ArrayList<>();
List<Integer> volume = new ArrayList<>();
// 我們希望每件物品都進行扁平化，是以首先周遊所有的物品
for (int i = 0; i < N; i++) {
// 擷取每件物品的出現次數
int val = s[i];
// 進行扁平化：如果一件物品規定的使用次數為 7 次，我們将其扁平化為三件物品：1*重量&1*價值、2*重量&2*價值、4*重量&4*價值
// 三件物品都不選對應了我們使用該物品 0 次的情況、隻選擇第一件扁平物品對應使用該物品 1 次的情況、隻選擇第二件扁平物品對應使用該物品 2 次的情況，隻選擇第一件和第二件扁平物品對應了使用該物品 3 次的情況 ...
for (int k = 1; k <= val; k *= 2) { //1 2 4 8 =>1 2 1+2 4 1+4 2+4 1+2+4 8 ..可以表示所有的數字
val -= k;
worth.add(w[i] * k);
volume.add(v[i] * k);
}
if (val > 0) {
worth.add(w[i] * val);
volume.add(v[i] * val);
}
}
// 0-1 背包問題解決方案
int[] dp = new int[C + 1];
for (int i = 0; i < worth.size(); i++) {
for (int j = C; j >= volume.get(i); j--) {
dp[j] = Math.max(dp[j], dp[j - volume.get(i)] + worth.get(i));
}
}
return dp[C];
}
}
與「直接将第 i 物品拆分為 s[i]件」的普通扁平化不同，二進制優化可以「将原本數量為s[i] 的物品拆分成
logs[i]
件」，使得我們轉化為 01 背包後的物品數量下降了一個數量級。
經過「二進制優化」的多重背包單秒能解決的資料範圍從
10^2
上升到
10^3
。