背包问题

算法笔记
动态规划, 算法, 背包问题

笔试时候遇到的动态规划问题比较多，背包问题比较有代表性，所以自己手动全部实现一遍，加深转移方程的推导与实现的记忆。下面依次介绍01背包（每种物品只有1个）、完全背包（每种物品有无限个）、多重背包（每种物品各有限制）

01背包

背包容量为cubage，物品种类为cate种，物品i花费为cost[i]，价值为value[i]
对于二维数组dp[i][j]表示容积为j放入前i种物品的最优解（价值最大值）
//代码中注释都说的比较详细，就不展开了，中途会插入一些参考链接

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int cubage = sc.nextInt();
	int cate = sc.nextInt(),i=1;
	int[] value = new int[cate+1];
	int[] cost = new int[cate+1];
	while(i<=cate){
		cost[i]=sc.nextInt();
		value[i]=sc.nextInt();
		i++;
	}
	parse01Normal(value,cost,cubage,cate);
}

下面是必须不装满的情况：

状态转移方程：dp[i][j]= max(dp[i-1][j-k*cost[i]]+k*value[i]) , k=0|1
如果需要还原最优解的物品，需要定义path[][]保存记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
private static void parse01Normal(int[] value, int[] cost, int cubage, int cate) {
	int i=0,j=0;
	//dp[i][j]表示容量为j且物品种类为i个时的最优解（最大价值）
	int[][] dp = new int[cate+1][cubage+1];
	//path[][]用于还原路径
	int[][]  path = new int[cate+1][cubage+1];
	for(i=0;i<=cate;i++){
		for(j=0;j<=cubage;j++){
			if(i==0||j==0)
				dp[i][j]=0;
			else{
				//dp[i][j]= max(dp[i-1][j-k*cost[i]]+k*value[i]) , k=0|1
				// 先默认不放入，即此时容量为j也只放前i-1个物品
				dp[i][j]=dp[i-1][j];
				//如果容积够，并且放入之后价值提升（j-cost[i]容积下放入前i-1个商品前提下,再放入当前商品），则放入
				if(cost[i]<=j && (dp[i-1][j-cost[i]]+value[i])>dp[i-1][j]) {
					dp[i][j] = dp[i - 1][j - cost[i]] + value[i];
					path[i][j]=1;
				}
			}
		}
	}
	i--;j--;
	while(i>0 && j>0){
		if(path[i][j]==1){
			System.out.print(i+ "->");
			j-=value[i];
		}
		i--;
	}
//        for(i=1;i<=cate;i++){
//            for(j=1;j<=cubage;j++) {
//                System.out.print(dp[i][j]+" ");
//            }
//            System.out.println();
//        }
}

必须装满

此时相当于必须从[0][0]位开始转移方程，可以在初始化的时候讲第一行[0][1~cubage]赋值为-1，在判断转移条件的时候如果为-1则不转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private static void parse01Full(int[] value, int[] cost, int cubage, int cate) {
	int i=0,j=0;
	//dp[i][j]表示容量为j且物品种类为i个时的最优解（最大价值）
	int[][] dp = new int[cate+1][cubage+1];
	//path[][]用于还原路径
	int[][]  path = new int[cate+1][cubage+1];
	dp[0][0]=0;
	//初始化的时候将不是从0开始
//        for(i=1;i<cate;i++)
//            dp[i][0]=-10000;
	//可以将非[0][0]值为-1，再判断转移的时候为-1则不转移
	//不过也可以直接赋为负无穷，这样判断大小的时候同样不会转移
	for(i=1;i<cubage;i++)
		dp[0][i]=-10000;
	for(i=1;i<=cate;i++){
		for(j=1;j<=cubage;j++){
			//dp[i][j]= max(dp[i-1][j-k*cost[i]]+k*value[i]) , k=0|1
			// 先默认不放入，即此时容量为j也只放前i-1个物品
			dp[i][j]=dp[i-1][j];
			//如果容积够，并且放入之后价值提升（j-cost[i]容积下放入前i-1个商品前提下再放入当前商品），则放入
			if(cost[i]<=j && (dp[i-1][j-cost[i]]+value[i])>dp[i-1][j]) {
				dp[i][j] = dp[i - 1][j - cost[i]] + value[i];
				path[i][j]=1;
			}
		}
	}
	for(i=1;i<=cate;i++){
		for(j=1;j<=cubage;j++) {
			System.out.print(dp[i][j]+" ");
		}
		System.out.println();
	}
}

滚动优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static void parse01Update(int[] value, int[] cost, int cubage, int cate) {
	int i=0,j=0,k=0;
	//dp[2][j] 当前价值只与上层相关，可优化为滚动2*cubage数组。
	int[][] dp = new int[2][cubage+1];
	for(i=0;i<=cate;i++){
		k=1-k;//也可转为k^1
		for(j=0;j<=cubage;j++){
			if(i==0||j==0)
				dp[k][j]=0;
			else{
				dp[k][j]=dp[1-k][j];
				if(cost[i]<=j && (dp[1-k][j-cost[i]]+value[i])>dp[1-k][j]) {
					dp[k][j] = dp[1-k][j-cost[i]] + value[i];
				}
			}
		}
	}
	System.out.println(dp[k][cubage]);
	//凡是可以滚动的，必定可以降维
}

一维数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static void parse01Optimize(int[] value, int[] cost, int cubage, int cate) {
	int i=0,j=0,k=0;
	//dp[] 只与上层左侧部分相关，优化为一维数组
	//max(dp[i-1][j-cost[i]]+value[i] , dp[i-1][j])
	int[] dp = new int[cubage+1];
	for(i=0;i<=cate;i++){
		//依赖上层保存的j-cost[i]信息，所以此时需要从后往前更新
		for(j=cubage;j>=cost[i];j--){
			if(i==0)
				dp[j]=0;
			else if(dp[j-cost[i]]+value[i]>dp[j])
				dp[j]=dp[j-cost[i]]+value[i];
		}
	}
	for(i=0;i<=cubage;i++)
		System.out.print(dp[i]+" ");
}

完全背包

状态转移方程：dp[i][j]= max(dp[i-1][j-k*cost[i]]+k*value[i]) , k=0|1…| (cubage/cost[i])
//对于完全背包，如果w[i]<=w[j] && v[i]>=v[j] 则可以直接无视j物品
注意下面的代码中有一次优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private static void parseWQNormal(int[] value, int[] cost, int cubage, int cate) {
	//注意此时物品并非只有一个，而是有无穷个，所以不只是放还是不放的问题
	//dp[i][j]= max(dp[i-1][j-k*cost[i]]+k*value[i]) , k=0|1...| (cubage/cost[i])
	int[][] dp = new int[cate+1][cubage+1];
	int i=0,j=0;
	for(i=0;i<=cate;i++){
		for(j=0;j<=cubage;j++){
			if(i==0||j==0)
				dp[i][j]=0;
			else {
				dp[i][j] = dp[i-1][j];
//                for(int k=1;k<=j/cost[i];k++){
//                    //注意此时j:0->cubage 其实每次都是以当前点重新计算，会重复计算
//                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-k*cost[i]]+k*value[i]);
//                }
				//计算dp[i][j]的时候其实考虑的是 max(dp[i-1][j-k*cost[i]]+k*value[i]) , k=0|1...| (cubage/cost[i])
				//计算dp[i][j+cost[i]]的时候考虑的是 max(dp[i-1][(j+cost[i])-k*cost[i]]+k*value[i]) , k=0|1...| (cubage/cost[i])
				//可以看出，dp[i][j+cost[i]] = max(dp[i][j]+value[i],dp[i-1][j+cost[i]])
				if (j >= cost[i] && (dp[i][j]<(dp[i][j-cost[i]]+value[i]))) { //注意与01背包的不同点
					dp[i][j] = dp[i][j-cost[i]]+value[i];
				}
			}
		}
	}
	for(i=1;i<=cate;i++){
		for(j=1;j<=cubage;j++) {
			System.out.print(dp[i][j]+" ");
		}
		System.out.println();
	}
}

同样可以用一维数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void parseWQOptimize(int[] value, int[] cost, int cubage, int cate) {
	int[] dp = new int[cubage+1];
	int i=0,j=0;
	for(i=0;i<=cate;i++){
		//依赖上次保存的同层j-cost[i]信息，所以此时需要从前往后更新
		//注意当j<=cost[i]时
		for(j=cost[i];j<=cubage;j++){//注意此处与01背包区别
			if(i==0)
				dp[j]=0;
			else{
				if(dp[j-cost[i]]+value[i]>=dp[j])
					dp[j]=dp[j-cost[i]]+value[i];
			}
		}
	}
	for(j=1;j<=cubage;j++) {
		System.out.print(dp[j]+" ");
	}
}

多重背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int cubage = sc.nextInt();
	int cate = sc.nextInt(),i=1;
	int[] value = new int[cate+1];
	int[] cost = new int[cate+1];
	int[] count = new int[cate+1];
	while(i<=cate){
		cost[i]=sc.nextInt();
		value[i]=sc.nextInt();
		count[i]=sc.nextInt();
		i++;
	}
	parseDCOptmize(value,cost,count,cubage,cate);
}

常规思路复杂度仍然是O(cubage*cate*sum(count[i]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static void parseDCNormal(int[] value, int[] cost, int[] count, int cubage, int cate) {
	int[][] dp = new int[cate+1][cubage+1];
	int i=0,j=0;
	//dp[i][j]= max(dp[i-1][j-k*cost[i]]+k*value[i]) , k=0|1...|count[i]
	for(i=0;i<=cate;i++){
		for(j=cost[i];j<=cubage;j++){
			if(i==0||j==0)
				dp[i][j]=0;
			else {
				int min = Math.min(count[i], j / cost[i]);
				for (int k = 0; k <= min; k++) {
					dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*cost[i]] + k * value[i]);
				}
			}
		}
	}
	for(i=1;i<=cate;i++){
		for(j=1;j<=cubage;j++) {
			System.out.print(dp[i][j]+" ");
		}
		System.out.println();
	}
}

一个容易想到的优化方案是转化为01背包，但是按照二进制分割，可以保证复杂度为O(cubage*sum(log2count[i]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private static void parseDCOptmize(int[] value, int[] cost, int[] count, int cubage, int cate) {
	//注意如果count[i]*cost[i]>cubage，其实等同于完全背包
	//此时需要用到二进制思想对物品进行分割，将一种多件物品转化为多种一件物品，转化为01背包问题
	//思考：二进制数每一位0表示不取，1表示取，这样我们就可以取遍所有的数
	//过程：对于第i件物品，将count[i]分解为若干个数的组合，使得参数可以组合成任意小于等于count[i]的件数
	//比如7=111，分解为001,010,100可表示任意<=7的数；13=1101，分解为001,010,100,0110前三数表示<=7,加上0110=6，可表示<=13的数
	//系数分别为1,2,4,...,2^(k-1),count[i]-2^k+1，k是满足count[i]-2^k+1>0的最大整数
	int i=1,j=0,cate_new=//下面给出转换代码
	int[] value_new = new int[1000];//取1000最大
	int[] cost_new = new int[1000];//取1000最大
	while(i<=cate){
		for(j=1;j<=count[i];j<<=1){//右移
			value_new[cate_new] = j*value[i];
			cost_new[cate_new]=j*cost[i];
			cate_new++;
			count[i]-=j;
		}
		if(count[i]>0){
			value_new[cate_new]=count[i]*value[i];
			cost_new[cate_new]=count[i]*cost[i];
		}else if(i==cate){
			cate_new--;
		}
		i++;
	}
//        for(i=0;i<=cate_new;i++)
//            System.out.print(value_new[i]+":"+cost_new[i]+" >");
//        System.out.println(cate_new);
	//之后便等同于01背包了
	int[] dp = new int[cubage+1];
	for(i=0;i<=cate_new;i++){
		//依赖上层保存的j-cost[i]信息，所以此时需要从后往前更新
		for(j=cubage;j>=cost_new[i];j--){
			if(i==0)
				dp[j]=0;
			else if(dp[j-cost_new[i]]+value_new[i]>dp[j])
				dp[j]=dp[j-cost_new[i]]+value_new[i];
		}
	}
	for(i=0;i<=cubage;i++)
		System.out.print(dp[i]+" ");
}

其实也有O(cate*cubage)的算法，参考多重背包单调队列优化

参考链接：

  1. 白话01背包
  2. 多重背包模板
  3. 流传颇广的背包九讲
  4. dp背包问题小结
  5. 背包问题详解
  6. 背包问题详解与实现
分享到