074背包dp-分组背包完全背包

题目一
// 分组背包(模版)
// 给定一个正数m表示背包的容量，有n个货物可供挑选
// 每个货物有自己的体积(容量消耗)、价值(获得收益)、组号(分组)
// 同一个组的物品只能挑选1件，所有挑选物品的体积总和不能超过背包容量
// 怎么挑选货物能达到价值最大，返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1757
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成”Main”，可以直接通过

public class Code01_PartitionedKnapsack {

	public static int MAXN = 1001;

	public static int MAXM = 1001;

	// arr[i][0] i号物品的体积
	// arr[i][1] i号物品的价值
	// arr[i][2] i号物品的组号
	public static int[][] arr = new int[MAXN][3];

	public static int[] dp = new int[MAXM];

	public static int m, n;

	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));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			m = (int) in.nval;
			in.nextToken();
			n = (int) in.nval;
			for (int i = 1; i <= n; i++) {
				in.nextToken();
				arr[i][0] = (int) in.nval;
				in.nextToken();
				arr[i][1] = (int) in.nval;
				in.nextToken();
				arr[i][2] = (int) in.nval;
			}
			Arrays.sort(arr, 1, n + 1, (a, b) -> a[2] - b[2]);
			out.println(compute1());
		}
		out.flush();
		out.close();
		br.close();
	}

	// 严格位置依赖的动态规划
	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];
	}

题目二

package class074;

import java.util.List;

// 从栈中取出K个硬币的最大面值和
// 一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币
// 每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里
// 给你一个列表 piles ，其中 piles[i] 是一个整数数组
// 分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k
// 请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少
// 测试链接 : https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/
public class Code02_MaximumValueOfKcoinsFromPiles {

	// 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];
	}

题目三

package class074;

// 完全背包(模版)
// 给定一个正数t，表示背包的容量
// 有m种货物，每种货物可以选择任意个
// 每种货物都有体积costs[i]和价值values[i]
// 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
// 返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1616
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Code03_UnboundedKnapsack {

	public static int MAXM = 10001;

	public static int MAXT = 10000001;

	public static int[] cost = new int[MAXM];

	public static int[] val = new int[MAXM];

	public static long[] dp = new long[MAXT];

	public static int t, m;

	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));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			t = (int) in.nval;
			in.nextToken();
			m = (int) in.nval;
			for (int i = 1; i <= m; i++) {
				in.nextToken();
				cost[i] = (int) in.nval;
				in.nextToken();
				val[i] = (int) in.nval;
			}
			out.println(compute2());
		}
		out.flush();
		out.close();
		br.close();
	}

	// 严格位置依赖的动态规划
	// 会空间不够，导致无法通过全部测试用例
	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];
	}

}

题目四

package class074;

// 正则表达式匹配
// 给你字符串s、字符串p
// s中一定不含有'.'、'*'字符，p中可能含有'.'、'*'字符
// '.' 表示可以变成任意字符，数量1个
// '*' 表示可以让 '*' 前面那个字符数量任意(甚至可以是0个)
// p中即便有'*'，一定不会出现以'*'开头的情况，也一定不会出现多个'*'相邻的情况(无意义)
// 请实现一个支持 '.' 和 '*' 的正则表达式匹配
// 返回p的整个字符串能不能匹配出s的整个字符串
// 测试链接 : https://leetcode.cn/problems/regular-expression-matching/
public static boolean isMatch3(String str, String pat) {
		char[] s = str.toCharArray();
		char[] p = pat.toCharArray();
		int n = s.length;
		int m = p.length;
		boolean[][] dp = new boolean[n + 1][m + 1];
		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];
	}