背包问题(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:

得到了我们想要的结果