动态规划

填满背包的最大价格

给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值
给定一个正数bag，表示一个载重bag的袋子，装的物品不能超过这个重量 返回能装下的最大价值

思路分析：
0-1背包问题主要涉及到两个问题的求解

a)求解背包所含物品的最大值：

利用动态规划求最优值的方法。假设用dp[N][V]来存储中间状态值,dp[i][j]表示前i件物品能装入容量为j的背包中的物品价值总和的最大值
(注意是最大值),则我们最终只需求知dp[i=N][j=V]的值，即为题目所求。
现在考虑动态规划数组dp[i][j]的状态转移方程：
假设我们已经求出前i-1件物品装入容量j的背包的价值总和最大值为dp[i-1][j],固定容量j的值不变，则对第i件物品的装法讨论如下：
首先第i件物品的重量weight[i]必须小于等于容量j才行，即
1、若weight[i]>j,则第i件物品肯定不能装入容量为j的背包，此时dp[i][j]=dp[i-1][j]
2、若weight[i]<=j,则首先明确的是这件物品是可以装入容量为j的背包的，那么如果我们将该物品装入，则有
dp[i][j]=dp[i-1][j-weight[i]]+value[i]
随之而来的问题是我们要判断第i件物品装到容量为j的背包后,背包内的总价值是否是最大？其实很好判断，即如果装了第i件物品后的总价值dp[i-1][
j-weight[i]]+value[i]>没装之前的总价值最大值dp[i-1][j]，则肯是最大的；反之则说明第i件物品不必装入容量为j的背包(
装了之后总价值反而变小，那么肯定就不需要装嘛)
故，状态转移方程如下：
dp[i][j] = (dp[i-1][j] > (dp[i-1][j-weight[i]]+value[i]))? dp[i-1][j]:(dp[i-1][j-weight[i]]+value[i])
注意：这里的前i件物品是给定次序的

b)求出背包中装入物品的编号

这里我们采用逆推的思路来处理，如果对于dp[i][j]>dp[i-1][j]，则说明第i个物品肯定被放入了背包，此时我们再考察dp[i-1][
j-weight[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


/**
	 * 0-1背包问题
	 * @param V	背包容量
	 * @param N	物品种类
	 * @param weight 物品重量
	 * @param value	物品价值
	 * @return
	 */
	public static String ZeroOnePack(int V,int N,int[] weight,int[] value){
		
		//初始化动态规划数组
		int[][] dp = new int[N+1][V+1];
		//为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
		for(int i=1;i<N+1;i++){
			for(int j=1;j<V+1;j++){
				//如果第i件物品的重量大于背包容量j,则不装入背包
				//由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
				if(weight[i-1] > j)
					dp[i][j] = dp[i-1][j];
				else
					dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);
			}
		}
		//则容量为V的背包能够装入物品的最大值为
		int maxValue = dp[N][V];
		//逆推找出装入背包的所有商品的编号
		int j=V;
		String numStr="";
		for(int i=N;i>0;i--){
			//若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
			if(dp[i][j]>dp[i-1][j]){
				numStr = i+" "+numStr;
				j=j-weight[i-1];
			}
			if(j==0)
				break;
		}
		return numStr;	
	}

多重背包

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
/**
	 * 第三类背包：多重背包
	 * 
	 * @param args
	 */
	public static int manyPack(int V,int N,int[] weight,int[] value,int[] num){
		//初始化动态规划数组
		int[][] dp = new int[N+1][V+1];
		//为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
		for(int i=1;i<N+1;i++){
			for(int j=1;j<V+1;j++){
				//如果第i件物品的重量大于背包容量j,则不装入背包
				//由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
				if(weight[i-1] > j)
					dp[i][j] = dp[i-1][j];
				else{
					//考虑物品的件数限制
					int maxV = Math.min(num[i-1],j/weight[i-1]);
					/*for(int k=0;k<maxV+1;k++){
						dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1]);
					}*/
					for(int k=0;k<maxV+1;k++){
						dp[i][j] = dp[i][j]>Math.max(dp[i-1][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1]) ? dp[i][j]:Math.max(dp[i-1][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1]);
					}
				}
			}
		}
		/*//则容量为V的背包能够装入物品的最大值为
		int maxValue = dp[N][V];
		int j=V;
		String numStr="";
		for(int i=N;i>0;i--){
			//若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
			while(dp[i][j]>dp[i-1][j]){
				numStr = i+" "+numStr;
				j=j-weight[i-1];
			}
			if(j==0)
				break;
		}*/
		return dp[N][V];
	}

三、完全背包

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
	 * 第二类背包：完全背包
	 * 思路分析：
	 * 01背包问题是在前一个子问题（i-1种物品）的基础上来解决当前问题（i种物品），
	 * 向i-1种物品时的背包添加第i种物品；而完全背包问题是在解决当前问题（i种物品）
	 * 向i种物品时的背包添加第i种物品。
	 * 推公式计算时，f[i][y] = max{f[i-1][y], (f[i][y-weight[i]]+value[i])}，
	 * 注意这里当考虑放入一个物品 i 时应当考虑还可能继续放入 i，
	 * 因此这里是f[i][y-weight[i]]+value[i], 而不是f[i-1][y-weight[i]]+value[i]。
	 * @param V
	 * @param N
	 * @param weight
	 * @param value
	 * @return
	 */
	public static String completePack(int V,int N,int[] weight,int[] value){
		//初始化动态规划数组
		int[][] dp = new int[N+1][V+1];
		//为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
		for(int i=1;i<N+1;i++){
			for(int j=1;j<V+1;j++){
				//如果第i件物品的重量大于背包容量j,则不装入背包
				//由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
				if(weight[i-1] > j)
					dp[i][j] = dp[i-1][j];
				else
					dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i-1]]+value[i-1]);
			}
		}
		//则容量为V的背包能够装入物品的最大值为
		int maxValue = dp[N][V];
		int j=V;
		String numStr="";
		for(int i=N;i>0;i--){
			//若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
			while(dp[i][j]>dp[i-1][j]){
				numStr = i+" "+numStr;
				j=j-weight[i-1];
			}
			if(j==0)
				break;
		}
		return numStr;
	}
	/**
	 * 完全背包的第二种解法
	 * 思路：
	 * 只用一个一维数组记录状态，dp[i]表示容量为i的背包所能装入物品的最大价值
	 * 用顺序来实现
	 */
	public static int completePack2(int V,int N,int[] weight,int[] value){
		
		//动态规划
		int[] dp = new int[V+1];
		for(int i=1;i<N+1;i++){
			//顺序实现
			for(int j=weight[i-1];j<V+1;j++){
				dp[j] = Math.max(dp[j-weight[i-1]]+value[i-1],dp[j]);
			}
		}
		return dp[V];
	}

__END__