DP經典回顧：背包問題

在學習動态規劃，但是老是把控不住狀态的定義和狀态方程的轉移，是以複習下背包問題，希望能有所提升。先記錄下常用的幾種類型吧，後面再慢慢記錄學習。

文章目錄

• 01背包
• 完全背包
• 多重背包
• 待續...
• 參考資料

01背包

1. 問題描述

有 N 件物品和一個容量為 V 的背包。放入第 i 件物品耗費的費用是 Ci，得到的價值是 Wi。求解将哪些物品裝入背包可使價值總和最大。

1. 問題分析

01背包的特點是：每種物品僅有一件，可以選擇放或不放。

• 定義狀态：dp[i, v] 表示前 i 件物品恰放入一個容量為 v 的背包可以獲得的最大價值。

• 狀态轉移方程：(非常重要，其他變種背包都是從此方程衍伸出的)

  dp[i][j]=max(dp[i-1][j],dp[i-1][j-Ci]+Wi)

怎麼了解這個方程呢？首先是将問題分解為子問題，就是若隻考慮第 i 件物品的政策（放或不放），那麼可以轉化為一個隻和前i−1件物品相關的問題。如果不放第 i 件物品，問題就轉化為“前i−1件物品放入容量為v的背包中”，是以其價值為 dp[i−1, v]；如果放第 i 件物品，那麼問題就轉化為“前i−1件物品放入剩下的容量為v−Ci的背包中”，此時能獲得的最大價值就是 dp[i−1, v−Ci]+Wi。

代碼如下：

static int m1_bag01(int v,int[] c,int[] w) {
		int dp[][]=new int[c.length+1][v+1];
		int N=c.length+1;
		int V=v+1;
		for (int i = 1; i < N; i++) {			
			for (int j = 0; j < V; j++) {
				//大的放不下，是以直接取上一次的結果
				if(j-c[i-1]<0)
					dp[i][j]=dp[i-1][j];
				else
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-c[i-1]]+w[i-1]);
			}
		}		
		return dp[c.length][v];
	}
           

1. 空間複雜度優化

可以發現，上述代碼的空間複雜度有點大，O（N*V）級别，如果給定背包的體積很大就容易超記憶體。如果隻用一個數組 dp[0 . . . v ]，就要保證第 i次循環結束後dp[v] 中表示的就是定義狀态 dp[i][v] 。這裡可以在每次主循環（從1周遊到v）中以遞減順序計算 dp[v]，這樣在計算 dp[v] 時使用的dp[v − Ci] 就是上一次循環儲存的狀态，即dp[i−1, v−Ci] 的值。

代碼如下：

static int m2_bag01(int v,int[] c,int[] w) {
		int dp[]=new int[v+1];
		int N=c.length;
		for (int i = 0; i < N; i++) {
		//倒序周遊，確定計算dp[j]時，dp[j-c[i]]存儲的是上一次即i-1的結果
			for (int j = v; j >=c[i]; j--) {
				dp[j]=Math.max(dp[j], dp[j-c[i]]+w[i]);
			}
		}		
		return dp[v];
	}
           

由于在後面的變種背包經常用到01背包的問題，是以定義一個方法，表示處理一件物品的01背包的過程：

//定義處理一個物品的01背包方法
//@參數說明：dp-狀态數組，c-目前物品體積，w-目前物品價值，v-背包體積
//@傳回：更新後的狀态數組
	static int[] one_bag01(int[] dp,int c,int w,int v) {
		for (int j = v; j >=c; j--) {
			dp[j]=Math.max(dp[j], dp[j-c]+w);
		}
		return dp;
	}
           

是以01背包代碼改寫如下：

static int bag01(int v,int[] c,int[] w) {
		int dp[]=new int[v+1];
		int N=c.length;
		for (int i = 0; i < N; i++) 
			dp=one_bag01(dp, c[i], w[i], v);		
		return dp[v];
	}
           

完全背包

1. 問題描述

有 N 種物品和一個容量為 V 的背包，每種物品都有無限件可用。放入第 i 種物品的費用是 Ci，價值是 Wi。求：将哪些物品裝入背包，可使這些物品的耗費的費用總和不超過背包容量，且價值總和最大。

1. 問題分析

轉化為01背包

可以這樣思考，因為第 i 種物品最多選 V/Ci件，于是可以把第 i 種物品重複V/Ci次加入到物品隊列重，然後求解這個新物品隊列的01背包問題。

• 狀态定義和之前一樣：

  dp[i, v] 表示前 i 件物品恰放入一個容量為 v 的背包可以獲得的最大價值。

• 是以狀态方程如下：

  dp[i][j]=max(dp[i-1][j-kCi]+k*Wi),其中0<=kCi<=v

總的複雜度是 O(NV Σ(V/Ci) ),還是可以優化的。

1. 算法優化

上述狀态方程其實等價為：dp[i][j]=max(dp[i-1][j],dp[i][j-Ci]+Wi),用類似01背包的空間優化方法，可以用一維數組表示。代碼也非常類似，就是把逆序周遊改為正序周遊即可。先看代碼，如下：

static int fullbag(int v,int[] c,int[] w) {
	int dp[]=new int[v+1];
	int N=c.length;
	for (int i = 0; i < N; i++) {
		//正序周遊，確定物品可以重複選
		for (int j = c[i]; j <V; j++) {
			dp[j]=Math.max(dp[j], dp[j-c[i]]+w[i]);
		}
	}		
	return dp[v];
}	
           

為什麼正序周遊就是完全背包了呢？01背包逆序周遊說白了是為了保證每件物品隻選一次，因為在選第i件物品用到的之前的狀态dp[v − Ci]是沒更新過的（或者說是在上一個狀态更新的），說明其是沒選過第i件物品。而完全背包的特點恰是每種物品可選無限件，是以在加選一件第 i 種物品時，正需要一個可能已選入第 i 種物品的子結果dp[i, v − Ci]，是以就可以并且必須采用j以v遞增的順序循環。

同樣在後面的變種背包經常用到完全背包的問題，是以定義一個方法，表示處理一件物品完全背包的過程：

//定義處理一個物品的完全背包方法
//@參數說明：dp-狀态數組，c-目前物品體積，w-目前物品價值，v-背包體積
//@傳回：更新後的狀态數組
static int[] one_fullbag(int[] dp,int c,int w,int v) {
	for (int j = c; j<=v; j++) {
		dp[j]=Math.max(dp[j], dp[j-c]+w);
	}
	return dp;
}
           

是以完全背包代碼更新如下：

static int fullbag(int v,int[] c,int[] w) {
	int dp[]=new int[v+1];
	int N=c.length;
	for (int i = 0; i < N; i++) 
		dp=one_fullbag(dp, c[i], w[i], v);
	return dp[v];
}
           

多重背包

1. 問題描述

有 N 種物品和一個容量為V的背包。第 i 種物品最多有 Mi 件可用，每件耗費的空間是 Ci，價值是 Wi。求解将哪些物品裝入背包可使這些物品的耗費的空間總和不超過背包容量，且價值總和最大。

1. 問題分析

首先是一般思路，轉化為01背包。其實這個狀态方程和完全背包的一樣，隻不過每件物品的個數有限制而已。

• 狀态轉移方程：

  dp[i][j]=max(dp[i-1][j-kCi]+k*Wi),其中0<=k<=mi

換個思路，多重背包其實可以認為是01背包和完全背包的結合，因為當物品 i 的Ci*Mi比v大時，處理這件物品就是個完全背包的過程，如比v小，那就可以轉化為k件物品 i 的01背包問題。那麼解題就很清晰了。

1. 代碼優化

雖然換了個思路，但是處理起來的時間複雜度還是有點大，這裡采用一個二進制優化的思路：

将第 i 種物品分成若幹件 01 背包中的物品，其中每件物品有一個系數。這件物品的費用和價值均是原來的費用和價值乘以這個系數。令這些系數分别為1, 2, 22. . . 2k−1, Mi − 2k + 1，且 k 是滿足 Mi − 2k + 1 > 0 的最大整數。例如，如果 Mi 為 13，則相應的 k = 3，這種最多取 13 件的物品應被分成系數分别為 1, 2, 4, 6 的四件物品。分成的這幾件物品的系數和為 Mi，表明不可能取多于 Mi 件的第 i 種物品。這種方法也能保證對于 0 . . . Mi 間的每一個整數，均可以用若幹個系數的和表示。

通過上訴方法，可以将處理每件物品的時間複雜度降低為O（v*logMi）的級别。

代碼如下：

//v-背包容量，c-物品體積，w-物品價值，m-每個物品最多使用次數
static int mulbag(int v,int[] c,int[] w,int[] m) {	
	int dp[]=new int[v+1];
	int N=c.length;
	//處理N件物品
	for (int i = 0; i < N; i++) {
		//對于目前物品
		//如果c[i]*m[i],轉化為完全背包問題
		if(c[i]*m[i]>v) {
			dp=one_fullbag(dp, c[i], w[i], v);
		}
		//否則轉化為01背包
		else {
			int k=1;
			//采用二進制思想分解
			while (k<m[i]) {					
				dp=one_bag01(dp, k*c[i], k*w[i], v);
				m[i]-=k;
				k=k*k;
			}
			dp=one_bag01(dp, m[i]*c[i], m[i]*w[i], v);
		}
	}		
	return dp[v];
}	
           

待續…

參考資料

https://www.cnblogs.com/-guz/p/9866118.html

https://github.com/tianyicui/pack