class086 动态规划中得到具体决策方案的技巧【算法】
算法讲解086【必备】动态规划中得到具体决策方案的技巧
code1 最长公共子序列
// 最长公共子序列其中一个结果
// 给定两个字符串str1和str2
// 输出两个字符串的最长公共子序列
// 如果最长公共子序列为空，则输出-1
// 测试链接 : https://www.nowcoder.com/practice/4727c06b9ee9446cab2e859b4bb86bb8
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成”Main”，可以直接通过
dp[i][j]：s1前i个和s2前j个的最长公共子序列
dp[i][j]=dp[i-1][j-1],s1[i]==s2[j]
dp[i][j]=max(dp[i-1][j],dp[i][j-1]
package class086;
// 最长公共子序列其中一个结果
// 给定两个字符串str1和str2
// 输出两个字符串的最长公共子序列
// 如果最长公共子序列为空，则输出-1
// 测试链接 : https://www.nowcoder.com/practice/4727c06b9ee9446cab2e859b4bb86bb8
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
// 讲解067 - 题目3，最长公共子序列长度
public class Code01_LCS {
public static int MAXN = 5001;
public static int[][] dp = new int[MAXN][MAXN];
public static char[] ans = new char[MAXN];
public static char[] s1;
public static char[] s2;
public static int n, m, k;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
s1 = br.readLine().toCharArray();
s2 = br.readLine().toCharArray();
n = s1.length;
m = s2.length;
lcs();
if (k == 0) {
out.println(-1);
} else {
for (int i = 0; i < k; i++) {
out.print(ans[i]);
}
out.println();
}
out.flush();
out.close();
br.close();
}
public static void lcs() {
dp();
k = dp[n][m];
if (k > 0) {
for (int len = k, i = n, j = m; len > 0;) {
if (s1[i - 1] == s2[j - 1]) {
ans[--len] = s1[i - 1];
i--;
j--;
} else {
if (dp[i - 1][j] >= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
}
}
}
// 填好dp表
public static void dp() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
}
}
code2 1125. 最小的必要团队
// 最小的必要团队
// 作为项目经理，你规划了一份需求的技能清单req_skills
// 并打算从备选人员名单people中选出些人组成必要团队
// 编号为i的备选人员people[i]含有一份该备选人员掌握的技能列表
// 所谓必要团队，就是在这个团队中
// 对于所需求的技能列表req_skills中列出的每项技能，团队中至少有一名成员已经掌握
// 请你返回规模最小的必要团队，团队成员用人员编号表示
// 你可以按 任意顺序 返回答案，题目数据保证答案存在
// 测试链接 : https://leetcode.cn/problems/smallest-sufficient-team/
把技能转为编码
把每个人的技能转为状态码
考察所有人
分为要第i号人，和不要第i号人
package class086;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
// 最小的必要团队
// 作为项目经理，你规划了一份需求的技能清单req_skills
// 并打算从备选人员名单people中选出些人组成必要团队
// 编号为i的备选人员people[i]含有一份该备选人员掌握的技能列表
// 所谓必要团队，就是在这个团队中
// 对于所需求的技能列表req_skills中列出的每项技能，团队中至少有一名成员已经掌握
// 请你返回规模最小的必要团队，团队成员用人员编号表示
// 你可以按 任意顺序 返回答案，题目数据保证答案存在
// 测试链接 : https://leetcode.cn/problems/smallest-sufficient-team/
public class Code02_SmallestSufficientTeam {
public static int[] smallestSufficientTeam(String[] skills, List<List<String>> people) {
int n = skills.length;
int m = people.size();
HashMap<String, Integer> map = new HashMap<>();
int cnt = 0;
for (String s : skills) {
// 把所有必要技能依次编号
map.put(s, cnt++);
}
// arr[i] : 第i号人掌握必要技能的状况，用位信息表示
int[] arr = new int[m];
for (int i = 0, status; i < m; i++) {
status = 0;
for (String skill : people.get(i)) {
if (map.containsKey(skill)) {
// 如果当前技能是必要的
// 才设置status
status |= 1 << map.get(skill);
}
}
arr[i] = status;
}
int[][] dp = new int[m][1 << n];
for (int i = 0; i < m; i++) {
Arrays.fill(dp[i], -1);
}
int size = f(arr, m, n, 0, 0, dp);
int[] ans = new int[size];
for (int j = 0, i = 0, s = 0; s != (1 << n) - 1; i++) {
// s还没凑齐
if (i == m - 1 || dp[i][s] != dp[i + 1][s]) {
// 当初的决策是选择了i号人
ans[j++] = i;
s |= arr[i];
}
}
return ans;
}
// arr : 每个人所掌握的必要技能的状态
// m : 人的总数
// n : 必要技能的数量
// i : 当前来到第几号人
// s : 必要技能覆盖的状态
// 返回 : i....这些人，把必要技能都凑齐，至少需要几个人
public static int f(int[] arr, int m, int n, int i, int s, int[][] dp) {
if (s == (1 << n) - 1) {
// 所有技能已经凑齐了
return 0;
}
// 没凑齐
if (i == m) {
// 人已经没了，技能也没凑齐
// 无效
return Integer.MAX_VALUE;
}
if (dp[i][s] != -1) {
return dp[i][s];
}
// 可能性1 : 不要i号人
int p1 = f(arr, m, n, i + 1, s, dp);
// 可能性2 : 要i号人
int p2 = Integer.MAX_VALUE;
int next2 = f(arr, m, n, i + 1, s | arr[i], dp);
if (next2 != Integer.MAX_VALUE) {
// 后续有效
p2 = 1 + next2;
}
int ans = Math.min(p1, p2);
dp[i][s] = ans;
return ans;
}
}
code3 最长递增子序列 T386911 最长上升子序列输出解
// 最长递增子序列字典序最小的结果
// 给定数组arr，设长度为n
// 输出arr的最长递增子序列
// 如果有多个答案，请输出其中字典序最小的
// 注意这道题的字典序设定（根据提交的结果推论的）：
// 每个数字看作是单独的字符，比如120认为比36的字典序大
// 保证从左到右每个数字尽量小
// 测试链接 : https://www.nowcoder.com/practice/30fb9b3cab9742ecae9acda1c75bf927
// 测试链接 : https://www.luogu.com.cn/problem/T386911
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成”Main”，可以直接通过
从右看就是最长递减子序列
ends数组，找到以ends[i]开头的递增序列长度
package class086;
// 最长递增子序列字典序最小的结果
// 给定数组arr，设长度为n
// 输出arr的最长递增子序列
// 如果有多个答案，请输出其中字典序最小的
// 注意这道题的字典序设定（根据提交的结果推论的）：
// 每个数字看作是单独的字符，比如120认为比36的字典序大
// 保证从左到右每个数字尽量小
// 测试链接 : https://www.nowcoder.com/practice/30fb9b3cab9742ecae9acda1c75bf927
// 测试链接 : https://www.luogu.com.cn/problem/T386911
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"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;
// 讲解072 - 最长递增子序列及其扩展
public class Code03_LIS {
public static int MAXN = 100001;
public static int[] nums = new int[MAXN];
public static int[] dp = new int[MAXN];
public static int[] ends = new int[MAXN];
public static int[] ans = new int[MAXN];
public static int n, k;
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) {
n = (int) in.nval;
for (int i = 0; i < n; i++) {
in.nextToken();
nums[i] = (int) in.nval;
}
lis();
for (int i = 0; i < k - 1; i++) {
out.print(ans[i] + " ");
}
out.println(ans[k - 1]);
}
out.flush();
out.close();
br.close();
}
// nums[...]
public static void lis() {
k = dp();
Arrays.fill(ans, 0, k, Integer.MAX_VALUE);
for (int i = 0; i < n; i++) {
if (dp[i] == k) {
// 注意这里
// 为什么不用判断直接设置
// 有讲究，课上重点讲了
ans[0] = nums[i];
} else {
if (ans[k - dp[i] - 1] < nums[i]) {
// 注意这里
// 为什么只需要判断比前一位(ans[k-dp[i]-1])大即可
// 有讲究，课上重点讲了
ans[k - dp[i]] = nums[i];
}
}
}
}
// dp[i] : 必须以i位置的数字开头的情况下，最长递增子序列长度
// 填好dp表 + 返回最长递增子序列长度
public static int dp() {
int len = 0;
for (int i = n - 1, find; i >= 0; i--) {
find = bs(len, nums[i]);
if (find == -1) {
ends[len++] = nums[i];
dp[i] = len;
} else {
ends[find] = nums[i];
dp[i] = find + 1;
}
}
return len;
}
// ends[有效区]从大到小的
// 二分的方式找<=num的最左位置
public static int bs(int len, int num) {
int l = 0, r = len - 1, m, ans = -1;
while (l <= r) {
m = (l + r) / 2;
if (ends[m] <= num) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
}
code4 P1759 通天之潜水
// 潜水的最大时间与方案
// 一共有n个工具，每个工具都有自己的重量a、阻力b、提升的停留时间c
// 因为背包有限，所以只能背重量不超过m的工具
// 因为力气有限，所以只能背阻力不超过v的工具
// 希望能在水下停留的时间最久
// 返回最久的停留时间和下标字典序最小的选择工具的方案
// 注意这道题的字典序设定（根据提交的结果推论的）：
// 下标方案整体构成的字符串保证字典序最小
// 比如下标方案”1 120″比下标方案”1 2″字典序小
// 测试链接 : https://www.luogu.com.cn/problem/P1759
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成”Main”，可以直接通过
dp[i][j][k]：[1…n]重量不超过j，阻力不超过k，最大提留事件
要第i件：dp[i-1][j][k]
不用第i件：dp[i-1][j-a[i]][k-b[i]]+c[i]
package class086;
// 潜水的最大时间与方案
// 一共有n个工具，每个工具都有自己的重量a、阻力b、提升的停留时间c
// 因为背包有限，所以只能背重量不超过m的工具
// 因为力气有限，所以只能背阻力不超过v的工具
// 希望能在水下停留的时间最久
// 返回最久的停留时间和下标字典序最小的选择工具的方案
// 注意这道题的字典序设定（根据提交的结果推论的）：
// 下标方案整体构成的字符串保证字典序最小
// 比如下标方案"1 120"比下标方案"1 2"字典序小
// 测试链接 : https://www.luogu.com.cn/problem/P1759
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"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;
// 讲解069 - 多维费用背包
// 不做空间压缩的版本
// 无法通过全部测试用例
// 这个题必须做空间压缩
// 空间压缩的实现在Code04_Diving2
public class Code04_Diving1 {
public static int MAXN = 101;
public static int MAXM = 201;
public static int[] a = new int[MAXN];
public static int[] b = new int[MAXN];
public static int[] c = new int[MAXN];
public static int[][][] dp = new int[MAXN][MAXM][MAXM];
public static String[][][] path = new String[MAXN][MAXM][MAXM];
public static int m, v, n;
public static void build() {
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= v; k++) {
dp[i][j][k] = 0;
path[i][j][k] = null;
}
}
}
}
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();
v = (int) in.nval;
in.nextToken();
n = (int) in.nval;
build();
for (int i = 1; i <= n; i++) {
in.nextToken();
a[i] = (int) in.nval;
in.nextToken();
b[i] = (int) in.nval;
in.nextToken();
c[i] = (int) in.nval;
}
compute();
out.println(dp[n][m][v]);
out.println(path[n][m][v]);
}
out.flush();
out.close();
br.close();
}
// 普通版本的多维费用背包
// 为了好懂先实现不进行空间压缩的版本
public static void compute() {
String p2;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= v; k++) {
// 可能性1 : 不要i位置的货
// 先把可能性1的答案设置上
// 包括dp信息和path信息
dp[i][j][k] = dp[i - 1][j][k];
path[i][j][k] = path[i - 1][j][k];
if (j >= a[i] && k >= b[i]) {
// 可能性2 : 要i位置的货
// 那么需要:
// 背包总重量限制j >= a[i]
// 背包总阻力限制k >= b[i]
// 然后选了i位置的货，就可以获得收益c[i]了
// 可能性2收益 : dp[i-1][j-a[i]][k-b[i]] + c[i]
// 可能性2路径(p2) : path[i-1][j-a[i]][k-b[i]] + " " + i
if (path[i - 1][j - a[i]][k - b[i]] == null) {
p2 = String.valueOf(i);
} else {
p2 = path[i - 1][j - a[i]][k - b[i]] + " " + String.valueOf(i);
}
if (dp[i][j][k] < dp[i - 1][j - a[i]][k - b[i]] + c[i]) {
dp[i][j][k] = dp[i - 1][j - a[i]][k - b[i]] + c[i];
path[i][j][k] = p2;
} else if (dp[i][j][k] == dp[i - 1][j - a[i]][k - b[i]] + c[i]) {
if (p2.compareTo(path[i][j][k]) < 0) {
// 如果可能性2的路径，字典序小于，可能性1的路径
// 那么把路径设置成可能性2的路径
path[i][j][k] = p2;
}
}
}
}
}
}
}
}
code4 P1759 通天之潜水
// 潜水的最大时间与方案
// 一共有n个工具，每个工具都有自己的重量a、阻力b、提升的停留时间c
// 因为背包有限，所以只能背重量不超过m的工具
// 因为力气有限，所以只能背阻力不超过v的工具
// 希望能在水下停留的时间最久
// 返回最久的停留时间和下标字典序最小的选择工具的方案
// 注意这道题的字典序设定（根据提交的结果推论的）：
// 下标方案整体构成的字符串保证字典序最小
// 比如下标方案”1 120″比下标方案”1 2″字典序小
// 测试链接 : https://www.luogu.com.cn/problem/P1759
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成”Main”，可以直接通过
package class086;
// 潜水的最大时间与方案
// 一共有n个工具，每个工具都有自己的重量a、阻力b、提升的停留时间c
// 因为背包有限，所以只能背重量不超过m的工具
// 因为力气有限，所以只能背阻力不超过v的工具
// 希望能在水下停留的时间最久
// 返回最久的停留时间和下标字典序最小的选择工具的方案
// 注意这道题的字典序设定（根据提交的结果推论的）：
// 下标方案整体构成的字符串保证字典序最小
// 比如下标方案"1 120"比下标方案"1 2"字典序小
// 测试链接 : https://www.luogu.com.cn/problem/P1759
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"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;
// 本文件做了空间压缩优化
// 可以通过全部测试用例
public class Code04_Diving2 {
public static int MAXN = 101;
public static int MAXM = 201;
public static int[] a = new int[MAXN];
public static int[] b = new int[MAXN];
public static int[] c = new int[MAXN];
public static int[][] dp = new int[MAXM][MAXM];
public static String[][] path = new String[MAXM][MAXM];
public static int m, v, n;
public static void build() {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= v; j++) {
dp[i][j] = 0;
path[i][j] = null;
}
}
}
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();
v = (int) in.nval;
in.nextToken();
n = (int) in.nval;
build();
for (int i = 1; i <= n; i++) {
in.nextToken();
a[i] = (int) in.nval;
in.nextToken();
b[i] = (int) in.nval;
in.nextToken();
c[i] = (int) in.nval;
}
compute();
out.println(dp[m][v]);
out.println(path[m][v]);
}
out.flush();
out.close();
br.close();
}
// 多维费用背包的空间压缩版本
// 请务必掌握空间压缩技巧
// 之前的课讲了很多遍了
public static void compute() {
String p2;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= a[i]; j--) {
for (int k = v; k >= b[i]; k--) {
if (path[j - a[i]][k - b[i]] == null) {
p2 = String.valueOf(i);
} else {
p2 = path[j - a[i]][k - b[i]] + " " + String.valueOf(i);
}
if (dp[j][k] < dp[j - a[i]][k - b[i]] + c[i]) {
dp[j][k] = dp[j - a[i]][k - b[i]] + c[i];
path[j][k] = p2;
} else if (dp[j][k] == dp[j - a[i]][k - b[i]] + c[i]) {
if (p2.compareTo(path[j][k]) < 0) {
path[j][k] = p2;
}
}
}
}
}
}
}
2023-12-22 20:51:34
版权声明：本文为博主作者：日星月云原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/qq_51625007/article/details/135151225
