请教一个随机抽题问题

[ydpro]

题库中有 N 条是数据 有一个总分，可以随意设置（例：100 分） 有一个题目数量，可以随意设置（例：20 个） 如何实现从题库中随机抽 20 道题，这 20 道题总分满足 100 ？ 有什么比较好的解法，求推荐！！

[murmur]

需求不合理，建议拿需求出来，一般的考卷是成组出题的，填空、选择、计算这样，只要分组确定了，每一组题目的分值也是确定的

不要为了提问随随便便想需求，直接把具体场景抛出来说

[jiangboenoch]

@murmur 这不应该是个算法题吗，为啥谈需求。n 个随机自然数(>=20)，随机从 n 中取出 20 个数，要求 20 个数返回的和刚好等于 100，如果所有的排列组合都不满足和等于 100，返回 false 。PS：拓展--要求对每个不同组合进行计数

[murmur]

@jiangboenoch 需求和算法是有区别的，考试不仅要分数加起来满足总值，还要考点覆盖当前考纲或者是特定章节内容

一个考试 150 分，全出计算题和实验题这样的主观题，然后每个题的分值不能调整，我倒是想见识下什么考试这么智障

实际上算法不需要按背包那样装满 100 分，比如我装满了 102 分，但是最后一道题是难度系数报表，那很简单，最后一个题从 9 分改成 7 分就可以了

[ydpro]

@murmur 具体场景：从题库中随机抽取指定题目，这些题目分数加起来满足用户指定的总分
背景：
用户可以设置题库
用户可以指定随机抽题的题目数量
用户可以指定随机抽题题目数量的总分是多少

场景描述：
后台有一个数据表，用户输入的题目会保存在表中，每道题目都有标题，选项，分数
用户要从题库中抽取 N(比如 20)道题，这 N 道题分数加起来要满足用户指定的总分（比如 100 分），请问有什么比较好的解法吗？

[Anshi]

这不是典型的 two sum 问题么。。。。先算出分数组合，再随机抽题目

[ydpro]

@jiangboenoch 对，请问有什么比较好的解法吗？

[maplerecall]

简单的思路：按分值和题数 dfs 出若干组合，随机抽一种组合，再随机每个分值对应的题目

[jiangboenoch]

@Anshi #5 细想了下，还真不一样，首先这个题不能去重，因为可以满足 32212=10 的情况，

而且穷举所有的排列组合，已知单个数最大是 81 最小是 1，所有的排列组合先穷举出来。可能没有 80²º，但是先穷举不可取。

我的方案是组合进行排序，然后单指针循环组合。
将题库的分值进行计数，当组合递归到计数结束时，结束循环。

[murmur]

@Anshi 这就是问题所在了，如果分数组合是要抽的

那么题目的分数确定是为什么？题型不同还是难度不同？

你抽了 20 个简单题，他抽了 10 个高难题，或者你抽了 20 个选择题，他抽了 30 个填空，这考试怕不是毫无公平性可言

所以我一开始就在想需求，每种题型的数量究竟是确定的还是抽的

[Anshi]

@murmur 可能目前需求对题目类型没有权重吧😂

[jiangboenoch]

@murmur #9 好哥哥要不去刷刷 leetcode 吧，你提的问题就相当于问 李雷为什么去找韩梅梅出去玩，不应该在家学习吗；为什么要把鸡蛋从 100 楼丢下去，这不是浪费粮食吗；

这是算法题题干，你谈需求。

[murmur]

@jiangboenoch 所以楼主也没说他是在刷题还是在做项目啊？

[jiangboenoch]

@murmur show me the code

// 用 js 做演示
const picker=(list)=>{
const counter={}
list.forEach(o=>{
if (counter.hasOwnProperty(o)){
counter[o]++
}else {
counter[o]=0
}
})
//用 5 个数做演示
const foo=[6,1,1,1,1]
// [6,1,1,1,1]
// [5,2,1,1,1]
// [4,3,1,1,1]
// [4,2,2,1,1]
// [3,3,2,1,1]

// 这里的递归需要再仔细想下，第一个递归下来就是 4 数之和 第二个递归下来就是 3 数之和 第三个递归下来就是 2 数之和
// 大概思路就是到这里，然后对 foo 进行计数，counter 对比，如果计数满足就 return
// 如果需要对 foo.length 做参数处理，那就写个生成 foo 的方法
}

[KousukeSakurako]

看起来像典型的动态规划问题, 如果题库里的题有类似这样的形式：5，6，7 分题都有无限个

[jiangboenoch]

@KousukeSakurako #14 我搜了哈动态规划，其中一条
“fucking-algorithm/动态规划详解进阶.md at master - GitHub”

“fucking-algorithm” 哈哈哈哈哈哈哈哈哈哈哈哈哈哈

[geelaw]

需要先定义什么“随机”，如果是所有可能的出题组合（顺序不同不算不同）中均匀选择一个组合，那么可以这样做：

1. 用动态规划计算 F(i, j, k) = 从前 i 道题目里选 j 道使总分是 k 有多少种组合。
2. 如果 F(N, 20, 100) 是零，则失败；否则运行递归算法 SampleCombination(N, 20, 100)，它工作方式如下：

SampleCombination(n, m, s):
令 n0, m0, s0 = n - 1, m, s
令 n1, m1, s1 = n - 1, m - 1, s - V(n)
令 p = F(n0, m0, s0) / F(n, m, s)
以 p 的概率不选择第 n 题且运行 F(n0, m0, s0)
如果没有不选择第 n 题，则选择之且运行 F(n1, m1, s1)

其中 V(n) 是题目 n 的分数。

[geelaw]

@geelaw * 且运行 F(...) => 且运行 SampleCombination(...)

[xz410236056]

概率论不是计算机必修课？
我第一反应是切比雪夫不等式

[ch2]

背包问题，全部组合都找出来，然后 random.choice

[jiangboenoch]

不好意思 没有认真审题，需要随机抽 20 满足，我的方法只能满足找出第一个满足 100 分的组合，无视我的思路 #13

[LxExExl]

https://www.geeksforgeeks.org/subset-sum-problem-dp-25/

N Sum, DP 就完事了。

[mgcnrx11]

https://www.jianshu.com/p/7fe9d3bb00ac 最近也在做类似的组卷算法，遗传算法好像是用得比较多的。关键是算法中找到适合自己的适应度计算方式

[justrand]

总分和题目数量都可以随意设置对吧，不用考虑题目类别以及难以程度导致的公平性吗？

[mgcnrx11]

@mgcnrx11 之前花了 2 天去尝试和调整这个算法，相信是能满足题主的要求的

[ydpro]

@justrand 嗯，都是可以随意设置，不需要考虑类别和难度

[maplelin]

这是求刚好装满背包情况的背包问题吧