博客

01背包问题

问题描述

有N件物品，每件物品的重量为weight[ i ]，价值为value[ i ]。现有一个容量为W的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。物品不重复。

分析

• 首先介绍sum[ i ][ j ]，sum[ i ][ j ]意思是：背包容量为j时，在前i件物品中取小于等于i件物品，此时取得的物品的价值最大，也就是此时背包里面物品的总价值最大。

现在有如下表格的5组数据，分别代表了5件物品，编号从1-5

现在假设背包容量为20，对应sum[ 0 ][ 20 ]，我们开始拿东西，从物品1开始，这里会有两种做法，拿或者不拿，如果拿了：此时背包里物品价值变成了sum[ 1 ][ 18 ]，它的值毫无疑问肯定是3，如果不拿：背包里物品的价值并没有变化，依旧是sum[ 0 ][ 20 ],也就是0

理解上面的分析后，下面给出状态转移方程：




问题：sum[ i ][ j ] = sum[ i-1 ][ j-weight[i] ]+value[ i ]怎么理解？


可以反过来理解，sum[ i ][ j ]是在取了第 i 件物品的总价值，在第 i 件物品被拿进背包之前我们只在前 i-1 件物品中选择。所以我们假设现在总价值为sum[ i-1 ][ j ],我们现在觉得拿第 i 个物品了，那么我们背包容量自然变为 j-weight[ i ]，同时还要加上第 i 件物品的价值value[ i ]

建议对应状态转移方程手动模拟下，加深理解

代码

public class BackPack01 {

	static int N=6;//物品有五件
	static int W=21;//背包容量为20
	static int weight[]= {0,2,3,4,5,9};//重量 2 3 4 5 9
	static int value[]= {0,3,4,5,8,10};//价值3 4 5 8 10
	
	public static void getValue() {
		int sum[][]= new int[N][W];//sum[i][j]意思是：背包容量为j时，在前i件物品中取小于等于i件物品，此时取得的物品的价值最大
		
		for(int i=1;i<N;i++) {
			for(int j=1;j<W;j++) {
				if(weight[i]>j) {//太重了，拿不了
					sum[i][j]=sum[i-1][j];
				}else {//拿：sum[i-1][j-weight[i]]+value[i]   不拿： sum[i-1][j]
					//拿为什么是k-1？  因为sum[i-1][j-weight[i]]可以理解为此时还没拿第i件的最大价值，当然我们要留weight[i]空间
					sum[i][j]=Math.max(sum[i-1][j-weight[i]]+value[i], sum[i-1][j]);
				}
			}
		}
		
		System.out.println(sum[5][20]);
	}
	
	public static void main(String[] args) {
		getValue();
	}
}

输出

26

优化

观察上面的状态转移方程可以发现 i 和 i-1 有着固定的对应关系，所以 i 其实可以省略掉，简化二维数组，采用一维数组sum[ j ]来记录总价值

问题1：这个和上面的方法有什么区别呢？


上面的方法直接用二维数组来记录总价值，记录后的数值会一直保存，这里用一维数组，会经过N（物品件数）次的刷新。举例来说，经过第一轮遍历（ i=1 那一轮），sum[ j ]数组中保存的数据意义为：背包容量为 j 时，只有第一个物品可以选择时的总价值。当 i =2 时就可以利用 sum 数组中保存的值（ i=1 ）来更新得到新的价值，直到 i 遍历结束。这样空间复杂度就会降低很多

问题2：为什么j从W-1开始遍历而不是1


这里的状态转移方程是：

sum[j]=Math.max(sum[j], sum[j-weight[i]]+value[i]);

可以看到sum[ j ]会用sum数组中小于 j 的数组元素来更新。同样假设现在sum数组已经经过第一轮遍历（ i=1，第一轮遍历假设不存在矛盾），如果我们从 j=1 开始遍历来求第二轮的数组（ i=2 ），假设sum[ 1 ]值不变（不拿），现在 j=2了，刚好拿了一个重量为 1 的物品，那么根据状态转移方程，现在要用sum[ 1 ]的值来更新sum[ 2 ]，可是此时的sum[ 1 ]是 i=2 时的值，更新需要 i=1时的值，这时就会出现矛盾

代码

	public static void getValue1() {
		int sum[]= new int[W];
		
		for(int i=1;i<N;i++) {
			for(int j=W-1;j>=1;j--) {
				if(weight[i]<=j) {
					sum[j]=Math.max(sum[j], sum[j-weight[i]]+value[i]);
				}
			}
		}
		
		System.out.println(sum[20]);
	}