随机试卷
给定分数列表scoreList，随机数量randomQuantity，随机分数randomScore；要求实现一个校验方法，判断分数列表中是否存在指定数量的题目，总分为randomScore
递归版本
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
| /**
* 生成校验
* @param
*
* @return
* <br>-----------------------------------------------------<br>
*
* @author: mujingya
* @date: 2024/4/2 16:25
*/public static boolean generateCheck1(List<Integer> scoreList, int randomQuantity, int randomScore) {
// 分数列表 随机数量 随机分数 从 0位置 0分数开始
return generateCheckHelper(scoreList, randomQuantity, randomScore, 0, 0);
}
/**
* 辅助校验
*
* @param scoreList 所有的题目分数列表
* @param remainingQuantity 剩余数量
* @param randomScore 随机分数
* @param start
* @param currentScoreSum
* @author: mujingya
* @date: 2024/4/2 18:36
*/private static boolean generateCheckHelper(List<Integer> scoreList, int remainingQuantity, int randomScore, int start, int currentScoreSum) {
// 剩余题目数量为0时
if (remainingQuantity == 0) {
// 返回是否相等
return currentScoreSum == randomScore;
}
// start开始 i++
for (int i = start; i < scoreList.size(); i++) {
// 每次 剩余题目数量-1 start位置+1 分数累加
Integer currentScore = scoreList.get(i);
// 递归校验
boolean recursionRes = generateCheckHelper(scoreList, remainingQuantity - 1, randomScore, i + 1, currentScoreSum + currentScore);
if (recursionRes) {
// 返回true 即递归剩余题目数量为0分数符合 直接返回
return true;
}
// false 继续循环校验 i++
}
return false;
}
|
三维动态规划
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
| public static boolean generateCheck3(List<Integer> scoreList, int randomQuantity, int randomScore) {
// 分数列表长度
int n = scoreList.size();
// dp[i][j][k] 表示从前i个分数中选择k个是否可以组成总和为j
boolean[][][] dp = new boolean[n+1][randomScore+1][randomQuantity+1];
// 初始化
for (int i = 0; i <= n; i++) {
// 不选择任何分数时，总和为0是可能的
dp[i][0][0] = true;
}
// 动态规划填表
for (int i = 1; i <= n; i++) {
// 当前分数
int score = scoreList.get(i-1);
// 总分
for (int j = 0; j <= randomScore; j++) {
// 选择k个 从1开始 至少选择一个分数
for (int k = 1; k <= randomQuantity; k++) {
// 默认先不选择当前分数 dp继承之前的状态
dp[i][j][k] = dp[i-1][j][k];
// 总分减去当前分数>=0 即可以选择当前分数（第i个分数）
if (j - score >= 0) {
// （参数递减）i-1个分数 是否存在k-1个分数 总和为j-score 存在就true 不存在就继承之前状态
// dp[i][j][k] = dp[i][j][k] || dp[i-1][j-score][k-1];
dp[i][j][k] |= dp[i-1][j-score][k-1];
}
}
}
}
// 返回是否存在一种方式可以选择randomQuantity个分数使总和为randomScore
return dp[n][randomScore][randomQuantity];
}
|
二维动态规划
思路：假定题目列表为[1, 3 ,4, 2]，要求题目数量2个，总分为5分
第一步，初始化dp表，dp[j][k]表示是否存在k个组成总分j，即存在0个题目组成0分
| k/j | 0 | 1 | 2 |
|---|
| 0 | T | F | F |
| 1 | F | F | F |
| 2 | F | F | F |
| 3 | F | F | F |
| 4 | F | F | F |
| 5 | F | F | F |
第二步，循环分数列表 动态规划填表 （每次循环为在(0,i]范围查找 更新dp表）
不再考虑0的行和列
在[1]查找，
是否存在1个组成1分？T
是否存在1个组成2分？
是否存在1个组成3分？
是否存在1个组成4分？
是否存在1个组成5分？
是否存在2个组成1分？
是否存在2个组成2分?
是否存在2个组成3分?
是否存在2个组成4分?
是否存在2个组成5分?
| k/j | 0 | 1 | 2 |
|---|
| 0 | T | F | F |
| 1 | F | T | F |
| 2 | F | F | F |
| 3 | F | F | F |
| 4 | F | F | F |
| 5 | F | F | F |
第三步，循环分数列表 动态规划填表 （每次循环为在(0,i]范围查找 更新dp表）
在[1,3]查找，
是否存在1个组成1分？T
是否存在1个组成2分？
是否存在1个组成3分？T
是否存在1个组成4分？
是否存在1个组成5分？
是否存在2个组成1分？
是否存在2个组成2分?
是否存在2个组成3分?
是否存在2个组成4分? T
是否存在2个组成5分?
| k/j | 0 | 1 | 2 |
|---|
| 0 | T | F | F |
| 1 | F | T | F |
| 2 | F | F | F |
| 3 | F | T | F |
| 4 | F | F | T |
| 5 | F | F | F |
第四步，循环分数列表 动态规划填表 （每次循环为在(0,i]范围查找 更新dp表）
在[1,3,4]查找，
是否存在1个组成1分？T
是否存在1个组成2分？
是否存在1个组成3分？T
是否存在1个组成4分？T
是否存在1个组成5分？
是否存在2个组成1分？
是否存在2个组成2分?
是否存在2个组成3分?
是否存在2个组成4分? T
是否存在2个组成5分? T （这一步就确定了）
| k/j | 0 | 1 | 2 |
|---|
| 0 | T | F | F |
| 1 | F | T | F |
| 2 | F | F | F |
| 3 | F | T | F |
| 4 | F | T | T |
| 5 | F | F | T |
第五步，循环分数列表 动态规划填表 （每次循环为在(0,i]范围查找 更新dp表）
在[1,3,4,2]查找，
是否存在1个组成1分？T
是否存在1个组成2分？T
是否存在1个组成3分？T
是否存在1个组成4分？T
是否存在1个组成5分？
是否存在2个组成1分？
是否存在2个组成2分?
是否存在2个组成3分? T
是否存在2个组成4分? T
是否存在2个组成5分? T
| k/j | 0 | 1 | 2 |
|---|
| 0 | T | F | F |
| 1 | F | T | F |
| 2 | F | T | F |
| 3 | F | T | T |
| 4 | F | T | T |
| 5 | F | F | T |
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
| public static boolean generateCheck(List<Integer> scoreList, int randomQuantity, int randomScore) {
// 题目总数量 小于 随机数量 直接返回false
if (scoreList.size() < randomQuantity){
return false;
}
int sum = scoreList.stream().mapToInt(Integer::intValue).sum();
// 题目总分数 小于 随机分数 直接返回false
if (sum < randomScore){
return false;
}
// 分数列表长度
int n = scoreList.size();
// dp[j][k] 表示 是否存在k个 组成总分j
boolean[][] dp = new boolean[randomScore + 1][randomQuantity + 1];
dp[0][0] = true;
// 循环分数列表 动态规划填表 （每次循环为在(0,i]范围查找 更新dp表）
for (int i = 1; i <= n; i++) {
// 当前分数
int score = scoreList.get(i - 1);
// j为总分 从最大开始
for (int j = randomScore; j >= score; j--) {
// 选择k个 从1开始
for (int k = 1; k <= randomQuantity; k++) {
// 前i个分数中 是否存在k-1个分数总和为j-score（即依赖上次的） 或 是否存在k个分数 总和为j
// dp[j][k] = dp[j][k] || dp[j - score][k - 1];
dp[j][k] |= dp[j - score][k - 1];
}
}
}
return dp[randomScore][randomQuantity];
}
|
需求实际场景
给定题目列表，随机生成符合条件的（数量和分数）具体题目列表
思路是打乱题目，再获取匹配的第一组
递归版本
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 List<QuestionDto> generateRandomQuestions1(List<QuestionDto> allQuestionList, int randomQuantity, int randomScore) {
Random random = new Random();
// 随机打乱题库 增加随机性
Collections.shuffle(allQuestionList, random);
List<QuestionDto> result = new ArrayList<>();
generateHelper(allQuestionList, randomQuantity, randomScore, 0, 0, new ArrayList<>(), result);
return result.isEmpty() ? null : result;
}
/**
* @param allQuestionList 所有的题目列表（题库）
* @param remainingQuantity 递归 剩余需要选取的题目数量
* @param randomScore 随机分数
* @param start 当前递归的起始位置下标 避免重复选取题目 (分别从0，1，2，3...开始)
* @param currentScoreSum 当前分数总和
* @param currentList 当前 已选取的题目组合列表
* @param result
*
* @return
*/
private static boolean generateHelper(List<QuestionDto> allQuestionList, int remainingQuantity, int randomScore, int start, int currentScoreSum, List<QuestionDto> currentList, List<QuestionDto> result) {
// 剩余数量为0 这轮组合完毕
if (remainingQuantity == 0) {
// 判断是否符合分数的条件
if (currentScoreSum == randomScore) {
// 符合条件 立即返回
result.addAll(currentList);
return true; }
return false;
}
// 循环问题列表
for (int i = start; i < allQuestionList.size(); i++) {
// 当前问题
QuestionDto question = allQuestionList.get(i);
// 当前问题分数
int currentScore = Integer.parseInt(question.getScore());
if (currentScoreSum + currentScore > randomScore) {
// 分数和 超过目标分数 跳过
continue;
}
// 否则 加入本次循环列表
currentList.add(question);
// 继续 剩余数量-1 循环位置+1 当前分数/列表增加
if (generateHelper(allQuestionList, remainingQuantity - 1, randomScore, i + 1, currentScoreSum + currentScore, currentList, result)) {
// 剩余数量为0 分数相等 立即返回
return true;
}
// 否则即为 剩余数量为0 分数不相等
// 回溯
currentList.remove(currentList.size() - 1);
}
return false;
}
|
三维动态规划
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
| public static List<QuestionDto> generateRandomQuestions(List<QuestionDto> allQuestionList, int randomQuantity, int randomScore) {
// 打乱
Collections.shuffle(allQuestionList, new Random());
int n = allQuestionList.size();
// i 当前考虑的 allQuestionList 中的索引
// k 需要选择的剩余问题数量
// j 选择需要达到的剩余分数
// 是否有可能从索引 i 开始选择k个问题 总分是j （和校验逻辑一样）
boolean[][][] dp = new boolean[n+1][randomQuantity+1][randomScore+1];
// k == 0 且 j == 0 不选择任何问题 总是 true
for (int i = 0; i <= n; i++) {
dp[i][0][0] = true;
}
// 动态规划填表 循环n次（问题数量）
for (int i = 1; i <= n; i++) {
// 对于每个问题 考虑所有可能的问题数量（k）和分数（j）组合
// 当前问题 i-1为真正索引位置
QuestionDto questionDto = allQuestionList.get(i - 1);
int currentScore = Integer.parseInt(questionDto.getScore());
// 问题从1开始
for (int k = 1; k <= randomQuantity; k++) {
// 是否可以在 包括当前问题 或 不包括当前问题 的情况下 达到特定的问题数量和总分
for (int j = 1; j <= randomScore; j++) {
// 对于索引为i的每个问题 有两种情况
// 1.不选择 即上一层（i-1）是否直接有符合情况的组合（k题j分） dp[i][k][j] = dp[i-1][k][j]。
dp[i][k][j] = dp[i-1][k][j];
// 2.选择 只有当前问题的分数不超过j时才可能
if (j >= currentScore) {
// 如果选择 需要检查在此之前上一层（i-1）是否存在 k-1个分数总和为j-currentScore （即就差现在这一题就是j分了） dp[i][k][j] = dp[i][k][j] || dp[i-1][k-1][j-currentScore]
dp[i][k][j] = dp[i][k][j] || dp[i-1][k-1][j-currentScore];
}
}
}
}
if (!dp[n][randomQuantity][randomScore]) {
return new ArrayList<>();
}
List<QuestionDto> result = new ArrayList<>();
// 剩余分数
int remainingScore = randomScore;
// 逆向回溯
for (int i = n, k = randomQuantity; i > 0 && k > 0; i--) {
// 当前考虑的问题 即位于i-1（真正的索引）的问题 是否真的需要
if (dp[i-1][k][remainingScore]) {
// 为true 则在没有当前问题的情况下 也能满足
// 如[1,3,4,2] 2道题5分 没有最后一个2也能满足
continue;
}
// dp[i-1][k][j] 为假但 dp[i][k][j] 为真
// 该问题是 应该是 结果的一部分
QuestionDto question = allQuestionList.get(i-1);
// 加入结果并减少剩余分数和数量
result.add(question);
remainingScore -= Integer.parseInt(question.getScore());
k--;
// 继续循环
}
return result;
}
|