背包問題(0-1背包)

商品詳情如圖, 背包體積為 21, 求背包可以裝入最大的價值的是多少

設背包為 bp(k, w)    k: 第k件商品, w: 背包剩餘重量

可以推出

可以畫圖

那我們的目标就是算出 B(3, 11) 的大小 和 B(3, 20) 的大小, 我們對 B(3, 11) :

這樣不停的算下去, 就可以得出 B(3, 11) 的大小, 就可以求得 B(4, 20) 的最大值

用代碼表示

public class bp {
	public static void main(String[] args) {
		int[] w = {2, 3, 4, 5, 9};		// 重量
		int[] v = {3, 4, 5, 8, 10};		// 體積
		int m = 21;						// 背包容積
		int maxValue = backPackI(m, w, v);
		System.out.println(maxValue);
	}
	public static int backPackI(int m, int[] w, int[] v) {
		int[][] bp = new int[w.length+1][m+1];
		for(int i = 1; i <= w.length; i++) {    
			for(int j = 0; j <= m; j++) {
				bp[i][j] = bp[i-1][j];    // 不拿或者放不下
				if(j >= w[i-1]) {         // 空間夠
					bp[i][j] = Math.max(bp[i][j], bp[i-1][ j-w[i-1] ] + v[i-1]);    // 選擇最大, 類似 B(3,20) 與 B(3,11) + 10 裡選大的
				}
			}
		}
		return bp[w.length][m];    // 相當于 B[4][20]
	}
}
           

我們運作程式, 将 bp 數組列印出來

可以看到, 結果應該是 27.

那可否繼續優化呢

我們從代碼中可以看到 隻使用了  bp[i][j] 和 bp[i-1][j];

可以将bp二維數組壓縮成一個隻有 2 行 的數組

public static int ScrollArray(int m, int[] w, int[] v) {
		int[][] bp = new int[2][m+1];
		int row = 0;
		for(int i = 1; i <= w.length; i++) {
			row ^= 1;
			for(int j = 0; j <= m; j++) {
				bp[row][j] = bp[row ^ 1][j];
				if(j >= w[i-1]) {
					bp[row][j] = Math.max(bp[row][j], bp[row^1][ j-w[i-1] ] + v[i-1]);
				}
			}
		}
		return bp[row][m];
}
           

列印數組bp:

其實我們發現隻有第二行才是我們需要的, 我們可以把二維數組壓縮為一維數組

public static int oneDimensionalArray(int m, int[] w, int[] v) {
		int[] bp = new int[m+1];
		for(int i = 1; i <= w.length; i++) {
			for(int j = m; j >= w[i-1]; j--) {
				bp[j] = Math.max(bp[j], bp[j - w[i-1]] + v[i-1]);
			}
		}
		return bp[m];
}
           

列印數組bp:

得到了我們想要的結果