01背包问题

基础背包

1
2
3
4
5
6
7
int[] dp = new int[weight+1];
for(int i=1;i<=n;i++){
    for(int j=weight;j>=nums[i-1];j--){
        dp[j] = Math.max(dp[j-nums[i-1]]+nums[i-1],dp[j]);
    }
}
return dp[weight];

目标和

leetcode 494

思路：见代码注释

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
// 新思路，转化为01背包问题
	// 思考1:
	// 虽然题目说nums是非负数组，但即使nums中有负数比如[3,-4,2]
	// 因为能在每个数前面用+或者-号
	// 所以[3,-4,2]其实和[3,4,2]会达成一样的结果
	// 所以即使nums中有负数，也可以把负数直接变成正数，也不会影响结果
	// 思考2:
	// 如果nums都是非负数，并且所有数的累加和是sum
	// 那么如果target>sum，很明显没有任何方法可以达到target，可以直接返回0
	// 思考3:
	// nums内部的数组，不管怎么+和-，最终的结果都一定不会改变奇偶性
	// 所以，如果所有数的累加和是sum，并且与target的奇偶性不一样
	// 那么没有任何方法可以达到target，可以直接返回0
	// 思考4(最重要):
	// 比如说给定一个数组, nums = [1, 2, 3, 4, 5] 并且 target = 3
	// 其中一个方案是 : +1 -2 +3 -4 +5 = 3
	// 该方案中取了正的集合为A = {1，3，5}
	// 该方案中取了负的集合为B = {2，4}
	// 所以任何一种方案，都一定有 sum(A) - sum(B) = target
	// 现在我们来处理一下这个等式，把左右两边都加上sum(A) + sum(B)，那么就会变成如下：
	// sum(A) - sum(B) + sum(A) + sum(B) = target + sum(A) + sum(B)
	// 2 * sum(A) = target + 数组所有数的累加和
	// sum(A) = (target + 数组所有数的累加和) / 2
	// 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2
	// 那么就一定对应一种target的方式
	// 比如非负数组nums，target = 1, nums所有数累加和是11
	// 求有多少方法组成1，其实就是求，有多少种子集累加和达到6的方法，(1+11)/2=6
	// 因为，子集累加和6 - 另一半的子集累加和5 = 1(target)
	// 所以有多少个累加和为6的不同集合，就代表有多少个target==1的表达式数量
	// 至此已经转化为01背包问题了
	public static int findTargetSumWays4(int[] nums, int target) {
		int sum = 0;
		for (int n : nums) {
			sum += n;
		}
		if (sum < target || ((target & 1) ^ (sum & 1)) == 1) {
			return 0;
		}
		return subsets(nums, (target + sum) >> 1);
	}

	// 求非负数组nums有多少个子序列累加和是t
	// 01背包问题(子集累加和严格是t) + 空间压缩
	// dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
	public static int subsets(int[] nums, int t) {
		if (t < 0) {
			return 0;
		}
		int[] dp = new int[t + 1];
		dp[0] = 1;
		for (int num : nums) { // i省略了
			for (int j = t; j >= num; j--) {
				dp[j] += dp[j - num];
			}
		}
		return dp[t];
	}

最后一块石头的重量

leetcode 1049

思路：转化为找出一个数组中最接近和的一半的子序列和。答案就是sum - 2 * 子序列和，找最接近和的一半的子序列和就是01背包问题。背包容量为一半，然后找出价值最高的子序列和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int lastStoneWeightII(int[] stones) {
    int sum = 0;
    for (int stone : stones) {
        sum+=stone;
    }
    int near = findLSW(stones,sum/2);
    return sum - near - near;
}

private int findLSW(int[] stones, int i) {
    int[] dp = new int[i+1];
    for (int stone : stones) {
        for(int j=i;j>=stone;j--){
            dp[j] = Math.max(dp[j],dp[j-stone]+stone);
        }
    }
    return dp[i];
}

分组背包

模板题

同一个组的物品只能选一个，求最大价值。

思路：还是分为要跟不要。但是要的情况需要讨论要一组里的哪一个。所以dp[i][j] 中的i表示物品组，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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 严格位置依赖的动态规划
	public static int compute1() {
		int teams = 1;
		for (int i = 2; i <= n; i++) {
			if (arr[i - 1][2] != arr[i][2]) {
				teams++;
			}
		}
		// 组的编号1~teams
		// dp[i][j] : 1~i是组的范围，每个组的物品挑一件，容量不超过j的情况下，最大收益
		int[][] dp = new int[teams + 1][m + 1];
		// dp[0][....] = 0
		for (int start = 1, end = 2, i = 1; start <= n; i++) {
			while (end <= n && arr[end][2] == arr[start][2]) {
				end++;
			}
			// start ... end-1 -> i组
			for (int j = 0; j <= m; j++) {
				// arr[start...end-1]是当前组，组号一样
				// 其中的每一件商品枚举一遍
				dp[i][j] = dp[i - 1][j];
				for (int k = start; k < end; k++) {
					// k是组内的一个商品编号
					if (j - arr[k][0] >= 0) {
						dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - arr[k][0]] + arr[k][1]);
					}
				}
			}
			// start去往下一组的第一个物品
			// 继续处理剩下的组
			start = end++;
		}
		return dp[teams][m];
	}

	// 空间压缩
	public static int compute2() {
		// dp[0][...] = 0
		Arrays.fill(dp, 0, m + 1, 0);
		for (int start = 1, end = 2; start <= n;) {
			while (end <= n && arr[end][2] == arr[start][2]) {
				end++;
			}
			// start....end-1
			for (int j = m; j >= 0; j--) {
				for (int k = start; k < end; k++) {
					if (j - arr[k][0] >= 0) {
						dp[j] = Math.max(dp[j], arr[k][1] + dp[j - arr[k][0]]);
					}
				}
			}
			start = end++;
		}
		return dp[m];
	}

从栈中取出k个硬币的最大面值和

leetcode 2218

思路：以一个栈里面的硬币为分组。一组里面的元素就是拿一个硬币，两个硬币，三个硬币…得到的面值。一组我也只能拿一个。

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
   // piles是一组一组的硬币
// m是容量，表示一定要进行m次操作
// dp[i][j] : 1~i组上，一共拿走j个硬币的情况下，获得的最大价值
// 1) 不要i组的硬币 : dp[i-1][j]
// 2) i组里尝试每一种方案
// 比如，i组里拿走前k个硬币的方案 : dp[i-1][j-k] + 从顶部开始前k个硬币的价值和
// 枚举每一个k，选出最大值
public static int maxValueOfCoins1(List<List<Integer>> piles, int m) {
	int n = piles.size();
	int[][] dp = new int[n + 1][m + 1];
	for (int i = 1; i <= n; i++) {
		// i从1组开始（我们的设定），但是题目中的piles是从下标0开始的
		// 所以来到i的时候，piles.get(i-1)是当前组
		List<Integer> team = piles.get(i - 1);
		int t = Math.min(team.size(), m);
		// 预处理前缀和，为了加速计算
		int[] preSum = new int[t + 1];
		for (int j = 0, sum = 0; j < t; j++) {
			sum += team.get(j);
			preSum[j + 1] = sum;
		}
		// 更新动态规划表
		for (int j = 0; j <= m; j++) {
			// 当前组一个硬币也不拿的方案
			dp[i][j] = dp[i - 1][j];
			for (int k = 1; k <= Math.min(t, j); k++) {
				dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + preSum[k]);
			}
		}
	}
	return dp[n][m];
}

// 空间压缩
public static int maxValueOfCoins2(List<List<Integer>> piles, int m) {
	int[] dp = new int[m + 1];
	for (List<Integer> team : piles) {
		int t = Math.min(team.size(), m);
		int[] preSum = new int[t + 1];
		for (int j = 0, sum = 0; j < t; j++) {
			sum += team.get(j);
			preSum[j + 1] = sum;
		}
		for (int j = m; j > 0; j--) {
			for (int k = 1; k <= Math.min(t, j); k++) {
				dp[j] = Math.max(dp[j], dp[j - k] + preSum[k]);
			}
		}
	}
	return dp[m];
}

完全背包

模板题

一个物品可以重复取，求最大价值。

dp[i][j] = Max(dp[i-1][j],dp[i][j-w[i]]+v[i]) //拿了之后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
// 严格位置依赖的动态规划
	// 会空间不够，导致无法通过全部测试用例
	public static long compute1() {
		// dp[0][.....] = 0
		int[][] dp = new int[m + 1][t + 1];
		for (int i = 1; i <= m; i++) {
			for (int j = 0; j <= t; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j - cost[i] >= 0) {
					dp[i][j] = Math.max(dp[i][j], dp[i][j - cost[i]] + val[i]);
				}
			}
		}
		return dp[m][t];
	}

	// 空间压缩
	// 可以通过全部测试用例
	public static long compute2() {
		Arrays.fill(dp, 1, t + 1, 0);
		for (int i = 1; i <= m; i++) {
			for (int j = cost[i]; j <= t; j++) {
				dp[j] = Math.max(dp[j], dp[j - cost[i]] + val[i]);
			}
		}
		return dp[t];
	}

正则匹配

leetcode 10

思路：在dfs注解里面

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
63
64
65
66
67
68
69
70
71
72
73
74
public static boolean isMatch1(String str, String pat) {
		char[] s = str.toCharArray();
		char[] p = pat.toCharArray();
		return f1(s, p, 0, 0);
	}

	// s[i....]能不能被p[j....]完全匹配出来
	// p[j]这个字符，一定不是'*'
	public static boolean f1(char[] s, char[] p, int i, int j) {
		if (i == s.length) {
			// s没了
			if (j == p.length) {
				// 如果p也没了，返回true
				return true;
			} else {
				// p还剩下一些后缀
				// 如果p[j+1]是*，那么p[j..j+1]可以消掉，然后看看p[j+2....]是不是都能消掉
				return j + 1 < p.length && p[j + 1] == '*' && f1(s, p, i, j + 2);
			}
		} else if (j == p.length) {
			// s有后缀
			// p没后缀了
			return false;
		} else {
			// s有后缀
		    // p有后缀
			if (j + 1 == p.length || p[j + 1] != '*') {
				// s[i....]
				// p[j....]
				// 如果p[j+1]不是*，那么当前的字符必须能匹配：(s[i] == p[j] || p[j] == '?')
				// 同时，后续也必须匹配上：process1(s, p, i + 1, j + 1);
				return (s[i] == p[j] || p[j] == '.') && f1(s, p, i + 1, j + 1);
			} else {
				// 如果p[j+1]是*
				// 完全背包！
				// s[i....]
				// p[j....]
				// 选择1: 当前p[j..j+1]是x*，就是不让它搞定s[i]，那么继续 : process1(s, p, i, j + 2)
				boolean p1 = f1(s, p, i, j + 2);
				// 选择2: 当前p[j..j+1]是x*，如果可以搞定s[i]，那么继续 : process1(s, p, i + 1, j)
				// 如果可以搞定s[i] : (s[i] == p[j] || p[j] == '.')
				// 继续匹配 : process1(s, p, i + 1, j)
				boolean p2 = (s[i] == p[j] || p[j] == '.') && f1(s, p, i + 1, j);
				// 两个选择，有一个可以搞定就返回true，都无法搞定返回false
				return p1 || p2;
			}
		}
	}

	// 动态规划
	public boolean isMatch(String s1, String p1) {
        char[] s = s1.toCharArray();
        char[] p = p1.toCharArray();
        int n = s.length;
        int m = p.length;
        boolean[][] dp = new boolean[n+1][m+1];
        // s到头了 ， p还没结束
        dp[n][m] = true;
        for(int j =m-1;j>=0;j--){
            dp[n][j] = j+1 < m && p[j+1] == '*' && dp[n][j+2];
        }
        // 普遍情况
        for(int i = n-1;i>=0;i--){
            for(int j = m-1;j>=0;j--){
                if(j+1 == m || p[j+1] != '*'){
                    dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i+1][j+1];
                }else {
					// 完全背包
                    dp[i][j] = dp[i][j+2] || ( (s[i] == p[j] || p[j] == '.') && dp[i+1][j]);
                }
            }
        }
        return dp[0][0];
    }

通配符匹配

leetcode 44

思路： 还是一样的。先初始化边界条件。然后如果遇到不是’‘ 就正常判断 dp[i][j] = dp[i+1][j+1] && (s[i] == p[j] || p[j] == ‘？’);’ 。遇到就是完全背包问题，可以用匹配一个之后不移动j , 也可以直接跳过 。 dp[i][j] = dp[i][j+1] || dp[i+1][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
public boolean isMatch(String s1, String p1) {
     char[] s = s1.toCharArray();
     char[] p = p1.toCharArray();
     int n = s.length;
     int m = p.length;
     boolean[][] dp = new boolean[n+1][m+1];
     //填s1完了但p1没完
    dp[n][m] = true;
    for(int j =m-1;j>=0;j--){
        dp[n][j] = p[j] == '*' && dp[n][j+1];
    }
    //普遍情况
    for(int i =n-1;i>=0;i--){
        for(int j =m-1;j>=0;j--){
            if(p[j]!='*'){
	//不是* 就正常递推
                dp[i][j] = (s[i] == p[j] || p[j] == '?') && dp[i+1][j+1];
            }else {
	// 完全背包
                dp[i][j] = dp[i][j+1] || dp[i+1][j];
            }
        }
    }
    return dp[0][0];
}

干草问题

购买足量干草的最小花费

有n个提供干草的公司，每个公司都有两个信息

cost[i]代表购买1次产品需要花的钱

val[i]代表购买1次产品所获得的干草数量

每个公司的产品都可以购买任意次

你一定要至少购买h数量的干草，返回最少要花多少钱

测试链接 : https://www.luogu.com.cn/problem/P2918

思路：还是完全背包但是定义dp。 dp[i][j] 表示1….i公司购买严格等于j份甘草时花费最小。 那么最后只用遍历 h 到 m 找出最小值即可。 m = h + max(val[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
// dp[i][j] : 1...i里挑公司，购买严格j磅干草，需要的最少花费
	// 1) dp[i-1][j]
	// 2) dp[i][j-val[i]] + cost[i]
	// 两种可能性中选最小
	// 但是关于j需要进行一定的扩充，原因视频里讲了
	public static int compute1() {
		int[][] dp = new int[n + 1][m + 1];
		Arrays.fill(dp[0], 1, m + 1, Integer.MAX_VALUE);
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j - val[i] >= 0 && dp[i][j - val[i]] != Integer.MAX_VALUE) {
					dp[i][j] = Math.min(dp[i][j], dp[i][j - val[i]] + cost[i]);
				}
			}
		}
		int ans = Integer.MAX_VALUE;
		// >= h
		// h h+1 h+2 ... m
		for (int j = h; j <= m; j++) {
			ans = Math.min(ans, dp[n][j]);
		}
		return ans;
	}

	// 空间压缩
	public static int compute2() {
		Arrays.fill(dp, 1, m + 1, Integer.MAX_VALUE);
		for (int i = 1; i <= n; i++) {
			for (int j = val[i]; j <= m; j++) {
				if (dp[j - val[i]] != Integer.MAX_VALUE) {
					dp[j] = Math.min(dp[j], dp[j - val[i]] + cost[i]);
				}
			}
		}
		int ans = Integer.MAX_VALUE;
		for (int j = h; j <= m; j++) {
			ans = Math.min(ans, dp[j]);
		}
		return ans;
	}

多重背包

多重背包问题：就是有数量限制的完全背包。每个物品有一定数量，不能无限拿。

思路：每到一个物品就枚举拿多少个的情况，求出最大值即可。但这里没用枚举优化可能会超时

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
// 严格位置依赖的动态规划
// 时间复杂度O(n * t * 每种商品的平均个数)
public static int compute1() {
	// dp[0][....] = 0，表示没有货物的情况下，背包容量不管是多少，最大价值都是0
	int[][] dp = new int[n + 1][t + 1];
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= t; j++) {
			dp[i][j] = dp[i - 1][j];
			for (int k = 1; k <= c[i] && w[i] * k <= j; k++) {
				dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
			}
		}
	}
	return dp[n][t];
}

// 空间压缩
// 部分测试用例超时
// 因为没有优化枚举
// 时间复杂度O(n * t * 每种商品的平均个数)
public static int compute2() {
	for (int i = 1; i <= n; i++) {
		for (int j = t; j >= 0; j--) {
			for (int k = 1; k <= c[i] && w[i] * k <= j; k++) {
				dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i]);
			}
		}
	}
	return dp[t];
}

二进制分组优化枚举。假如一个货物有13个，那么可以拆分为 1，2，4，6 。然后将这四个数看出四个物品即可。转化为了01背包问题。

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
public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StreamTokenizer in = new StreamTokenizer(br);
       PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
       a=0;
       while(in.nextToken() != StreamTokenizer.TT_EOF){
           n = (int)in.nval;
           in.nextToken(); W = (int) in.nval;
           for(int i=1,v,w,m;i<=n;i++){
               in.nextToken(); v = (int) in.nval;
               in.nextToken(); w = (int) in.nval;
               in.nextToken(); m = (int) in.nval;
			// 转化
               for(int j = 1; m>=j ; j<<=1){
                   val[a] =  v*j;
                   weight[a++] = w*j;
                   m-=j;
               }
               if(m>0){
                   val[a] = m*v;
                   weight[a++] = w*m;
               }
           }
           out.println(compute());
       }
       out.flush();
       out.close();
       br.close();
   }

// 01背包
   public static int compute(){
       Arrays.fill(dp,0,W+1,0);
       for(int i = 0;i<a;i++){
           for(int j = W;j>=weight[i];j--){
               dp[j] = Math.max(dp[j],dp[j-weight[i]]+val[i]);
           }
       }
       return dp[W];
   }