高效多背包容器组卷系统及其组卷方法

技术领域

本发明涉及计算机在线组卷技术领域，具体的说是一种基于多背包容器组卷系统及其组卷方法。

背景技术

随着互联网的逐渐普及，学习资料利用互联网资源实现网络化，构建网络学习平台，来打破因为地理环境和发展因素造成的教育资源分布不均、师资力量短缺等问题。促进教育公平化以及中西部地区的教育发展。同时，东部沿海地区，因其具有良好的基础设施的优势，逐步试点“无纸化教育”以及“无纸化考试”等模式。

在传统的学习过程中，考试作为一种检验学习成果、评估学习成效的有效模式，已经被传承了近千年。而在互联网的浪潮下，如何实现考试的网络化、智能化、个性化也成了当务之急。在原有的传统组卷算法中，以背包问题为基础的组卷算法尤为众多。

背包问题是一种组合优化问题。问题可以简单描述为：给定一组物品和一个背包，每个物品有其对应的重量和价值，而背包则有其所能装载的重量上限。因此，我们要通过合理选择来使得在不超过背包装载量的上限下，背包所装载的价值尽可能地大。背包问题可以抽象成一个容器-物品填充模型，即当前可供选择的物品中，能否通过合理选择，使得容器被填满且其承载价值达到最大。

贪心算法是一种选择的策略，即在每次选择的时候都做出当前状态下的最优解，从全局来看，即做出当前状态下的局部最优解。在进行背包问题的求解时，使用贪心算法，计算每个物品的权值(物品价值除以物品体积)，优先放入权值较大物品来填充背包，来快速解决背包问题。

贪心算法可以描述为现有若干背包与若干物品，每个背包都有一定的容量，每个物品具有一定的价值，选择一种装填方式使得背包所装的物品价值和最大。

假设现有背包集合B与物品集合I。B中有m个元素，表示有m个背包。I 中有n个元素，表示有n件物品。B中每个元素的值即为该背包的容量，I中每个元素的值即为该物品的价值。记I中第i个0＜i≤m元素的容量为c_i，I中第j个>j。

故集合B可以表示为：B＝{c₁，c₂，c₃，…c_m}

集合I可以表示为：I＝{v₁,v₂,v₃，…v_n}

假设I中所有元素的和小于I中的元素个数，且I中的元素一定能填满B中的每个背包。

原始的背包填充方式为从B中选取一个背包B_i后，依次选取I中的每个物品>j放入背包B_i中，判断该物品是否适合该背包，重复这个过程直到背包B_i被填充满。再选择下一个背包重复以上过程直到集合B中所有背包都被填满。

在上述过程中，第1个背包需要尝试n件物品、第2个背包需要尝试(n-1) 件物品，以此类推，第m个背包需要尝试(n-m)件物品。故上述方法的选取次数为：化简得

故该方法的时间复杂度为

现要使背包中所有物品价值最大，则需使用贪心算法进行选择：

根据贪心算法定义可知，在每次进行物品选择的时候选择当前物品中价值最大的物品。每次选择的I_j都满足以下条件：I_j∈I，I_j＝max(I)

故在实际过程中，需要现对集合I进行排序操作，使用快速排序法，以物品价值降序进行排序，得到新的集合I：I＝{v₁,v₂,v₃，…v_n}

从集合B中选取背包B_i后，从I中选取前c_i件物品放入B_i中即可。对集合B>1+c₂+c₃+…+c_m

记为集合B中所有元素的平均值：

则选取次数可以表示为：

故利用贪心算法来解决背包问题的时间复杂度为：

在传统的组卷算法中，以单一题型作为物品，以试卷作为容器，来进行试卷生成：

构建试卷容器，以试卷总分为背包容量，然后以每题分数作为题目的价值来进行容器填充，当试卷容器中的题目中分数和达到了预先设置的卷面分数后，则组卷成功；若遍历完所有题目仍无法达到制定分数，则判定组卷失败。

理论上利用贪心算法能将背包问题的时间复杂度控制在但在实际生产环境中，题库数据存放在数据库中而非内存中，服务器与数据库通信的时间远远大于CPU计算时间。

假设服务器与数据库通信的时间复杂度为O(l),且有O(l)＞＞O(n)，则原算法的时间复杂度表示为：

且试题与试卷都不只有一种属性，假设组卷过程中涉及k类属性，若使用原算法，则需重复执行k次以满足组卷需求，其时间复杂度为：显而易见，过大的时间复杂度无法满足大量的在线制卷需求。

随着以背包问题为基础的组卷算法的实际应用，暴露出的问题除了效率低下之外，还有潜在的造成线程死锁的风险：在实验环境中，背包问题中的物品存放于内存中，遍历题目的操作能够迅速完成；而在实际生产环境中，题目存放于数据库之中。相交于从内存中读取，数据库的读写是一个极其缓慢的操作。在面对实际生产环境中存在的多线程、高并发组卷操作，传统组卷算法对数据库的反复读写，极易造成达到数据库连接上限，引起数据库堵塞，继而引发程序线程死锁，造成整个系统崩溃。

发明内容

针对上述问题，本发明提供了一种高效多背包容器组卷系统及其组卷方法，利用容器填充模块实现多个背包容器进行制卷，从而克服组卷的高复杂度，采用将试卷属性和试题属性写入数据库，实现试卷、试题数据一次性调取，节约时间，制卷可靠。

为达到上述目的，本发明采用的具体技术方案如下：

一种高效多背包容器组卷系统，其关键在于：包括电子试卷输入输出平台，所述电子试卷输入输出平台与服务器连接，所述服务器内设置有组卷模块，所述组卷模块与数据库连接。所述组卷模块包括容器填充模块、物品虚拟标记模块、本地虚拟标记模拟填充模块和控制反转组卷模块。所述电子试卷输入输出平台用于获取电子试卷框架，所述电子试卷框架设置有试卷要求和N个试题要求，所述试卷要求内设置有试卷属性，每一个所述试题要求内设置有对应的试题属性。

所述容器填充模块用于将电子试卷框架转换成容器试卷，所述容器试卷包括试卷容器和N个试题容器。

所述物品虚拟标记模块用于将所述容器试卷转换成虚拟标记试卷，所述虚拟标记试卷包括虚拟标记试卷容器和N个虚拟标记试题容器。

所述本地虚拟标记模拟填充模块用于将所述试卷属性填充至虚拟标记试卷容器，得到完整虚拟标记试卷容器；并将每一个所述试题属性填充至对应的虚拟标记试题容器中，得到N个完整虚拟标记试题容器。

所述控制反转组卷模块用于将完整虚拟标记试卷容器的试卷虚拟标记及试卷属性写入所述数据库，并从该数据库中调取与试卷属性对应的试卷数据至试卷容器；所述控制反转组卷模块还将N个完整虚拟标记试题容器的试题虚拟标记及所有试题属性写入所述数据库，并从所述数据库中调取与试题属性相同的试题数据至N个试题容器。

其中N＝1，2，3…。

通过上述设计，容器填充模块采用多背包容器进行填充，将试卷的试卷属性、试题属性分装在不同的背包容器中，增强试卷中各个属性的逻辑性，调理清晰。实现单次运行组卷算法来解决复数试卷的属性。

同时采用本地虚拟标记模拟填充模块将试卷属性和试题属性填充至虚拟容器中，结合反转组卷模块将容器的虚拟标记以及对应的属性写入数据库，实现试卷数据和试题数据一次调取，减少了数据库和服务器之间的通信次数，缩短了组卷时间，减小了服务器与数据库的压力，为将来的个性化在线组卷考试提供了有力的支持。

进一步描述，所述容器填充模块将所述试卷要求转换成试卷容器、将所述N 个试题要求分别转换成N个试题容器两个过程同时进行。

采用多个背包容器实现对试卷属性和N个试题属性进行同时描述，互不影响。

再进一步描述，所述试卷属性包括试卷科目、制卷人、监考人、考试时间、试卷总分数和试卷难度。

再进一步描述，每个所述试题属性包括试题编号、试题类型、试题知识点、试题难度、试题分值和试题命题人。

一种高效多背包容器组卷系统的组卷方法，其关键在于包括以下步骤：

S1：构建电子试卷构架，在所述电子试卷框架内设置有试卷要求、试卷属性、N个试题要求及N个试题要求对应的试题属性；将电子试卷构架输入到电子试卷输入输出平台；

S2：服务器内的容器填充模块将电子试卷框架转换成容器试卷，同时所述容器填充模块还将试卷要求转换成试卷容器，将N个试题要求分别转换成N个试题容器；

S3：服务器内的物品虚拟标记模块将步骤S2得到的容器试卷转换成虚拟标记试卷，同时还将步骤S2得到的试卷容器转换成虚拟标记试卷容器，将步骤S2 得到的N个试题容器分别转换成N个虚拟标记试题容器；

S4：服务器内的本地虚拟标记模拟填充模块将步骤S1中设置的试卷属性填充至步骤S3得到的虚拟标记试卷容器中，得到完整虚拟标记试卷容器；本地虚拟标记模拟填充模块还将步骤S1中设置的N个试题属性分别对应填充至步骤 S3得到的N个虚拟标记试题容器，得到N个完整虚拟标记试题容器；

S5：服务器内的控制反转组卷模块将完整虚拟标记试卷容器的试卷虚拟标记及其试卷属性写入所述数据库，控制反转组卷模块将N个完整虚拟标记试题容器的试题虚拟标记及其试题属性写入数据库；

S6：服务器根据步骤S5写入的所有数据在数据库中查询所有试卷数据信息和所有试题数据信息；

S7：设定试卷调取原则和试题调取原则，服务器内的控制反转组卷模块根据试卷属性和试卷数据信息，在所述数据库中调取与试卷属性对应的试卷数据至试卷容器中；同时控制反转组卷模块还根据所有试题属性和所有试题数据信息，在所述数据库中调取与所有试题属性分别对应的试题数据至N个试题容器中；

S8：将步骤S7得到的试卷数据、试题数据反馈至电子试卷输入输出平台，试卷数据、试题数据结合电子试卷框架得到电子试卷。其中，在进行试卷属性和试题属性进行填充时，服务器需要对试卷属性和试题属性是否全部填充完毕进行判断，直至填充完整。

通过构建电子试卷构架，将试卷属性、每个试题属性进行区分，再经过容器填充模块，使试卷属性和每个试题属性分别填充至不同的容器中，罗列出每个容器与所填充的属性的对应关系，每个容器相互独立，且同时存在。简化试卷复杂度。物品虚拟标记模块将每个容器转化成一个对应的虚拟标记，该虚拟标记可以是由字母、数字、符号组成的字符标记。每个虚拟标记互不相同。本地虚拟标记模拟填充模块将试卷属性和试题属性对应填充至转化成虚拟标记的容器中。控制反转组卷模块控制完整虚拟标记容器试卷，使所有的虚拟标记及对应的试卷属性或者试题属性录入到数据库中，控制反转组卷模块控制数据库根据录入的内容，实现试题数据和试卷数据一次性调取。实现一次性数据调取，减少了服务器和数据库之间的通信次数，提高了组卷效率和组卷正确性。算法能够控制制卷过程的开始与结束，简化制卷流程。

再进一步描述，步骤S6中所述的试卷数据信息为所述数据库中包含的与试卷属性对应的所有试卷、试卷总数量和每个试卷的属性权值；所述试题数据信息为所述数据库中包含的与所有试题属性分别对应的所有试题、试题数量和每个试题的属性权值。

再进一步描述，步骤S7中，采用贪心算法对所述数据库中的试卷和试题进行调取。

再进一步描述，所述贪心算法对所述数据库中试卷的试卷调取原则为：按照试卷的属性权值由高到低依次调取；所述贪心算法对所述数据库中试题的试题调取原则为：按照试题的属性权值由高到低依次调取。其中，属性权值的大小为人为自定义。

再进一步描述，步骤S6中查询到所述数据库中不存在与试卷属性对应的试卷数据时，调整试卷属性至临近的试卷属性，进行试卷数据调取；步骤S6中查询到所述数据库中不存在与试题属性对应的试题数据时，调整试题属性至临近的试题属性，进行试题数据调取。

再进一步描述，在所述电子试卷输入输出平台上连接有电子试卷显示器，所述电子试卷显示器用于显示电子试卷。

本发明的有益效果：本发明在传统的组卷算法中引入了多背包容器填充，通过多容器来实现多个属性进行同时组卷，使得极为复杂的组卷需求得以实现，还引入物品虚拟标记技术，将容器实体转化成对应的虚拟标记，来写入数据库，实现数据库对对应的属性要求的内容进行查询，并实现对应的数据调取。减少了服务器与数据库之间的通信次数，同时大大提高了算法的执行效率，减少了服务器与数据库的压力，为将来的个性化在线组卷考试提供了有力的支持。

附图说明

图1是本发明的系统结构框图；

图2是本发明的制卷流程框图；

图3是本发明的制卷方法流程图。

具体实施方式

下面结合附图对本发明的具体实施方式以及工作原理作进一步详细说明。

从图1可以看出，一种高效多背包容器组卷系统，其特征在于：包括电子试卷输入输出平台1，所述电子试卷输入输出平台1与服务器2连接，所述服务器2内设置有组卷模块3，所述组卷模块3与数据库4连接；所述组卷模块3包括容器填充模块3a、物品虚拟标记模块3b、本地虚拟标记模拟填充模块3c和控制反转组卷模块3d。在所述电子试卷输入输出平台1上连接有电子试卷显示器，所述电子试卷显示器用于显示电子试卷。

结合图1和图2可以看出，所述电子试卷输入输出平台1用于获取电子试卷框架，所述电子试卷框架设置有试卷要求和N个试题要求，所述试卷要求内设置有试卷属性，每一个所述试题要求内设置有对应的试题属性；

在本实施例中，所述容器填充模块3a用于将电子试卷框架转换成容器试卷，所述容器试卷包括试卷容器和N个试题容器；

在本实施例中，所述物品虚拟标记模块3b用于将所述容器试卷转换成虚拟标记试卷，所述虚拟标记试卷包括虚拟标记试卷容器和N个虚拟标记试题容器；即：虚拟标记试卷容器对应一个试卷虚拟标记，每个容器对应一个试题虚拟标记。

在本实施例中，所述本地虚拟标记模拟填充模块3c用于将所述试卷属性填充至虚拟标记试卷容器，得到完整虚拟标记试卷容器；并将每一个所述试题属性填充至对应的虚拟标记试题容器中，得到N个完整虚拟标记试题容器；

在本实施例中，所述控制反转组卷模块3d用于将完整虚拟标记试卷容器的试卷虚拟标记及试卷属性写入所述数据库4，并从该数据库4中调取与试卷属性对应的试卷数据至试卷容器；所述控制反转组卷模块3d还将N个完整虚拟标记试题容器的试题虚拟标记及所有试题属性写入所述数据库4，并从所述数据库4 中调取与试题属性相同的试题数据至N个试题容器。

在本实施例中，所述容器填充模块3a将所述试卷要求转换成试卷容器、将所述N个试题要求分别转换成N个试题容器两个过程同时进行。

优选地，所述试卷属性包括试卷科目、制卷人、监考人、考试时间、试卷总分数和试卷难度。

优选地，每个所述试题属性包括试题编号、试题类型、试题知识点、试题难度、试题分值和试题命题人。

一种高效多背包容器组卷系统的组卷方法，包括以下步骤：

S1：构建电子试卷构架，在所述电子试卷框架内设置有试卷要求、试卷属性、N个试题要求及N个试题要求对应的试题属性；将电子试卷构架输入到电子试卷输入输出平台；

S2：服务器2内的容器填充模块3a将电子试卷框架转换成容器试卷，同时所述容器填充模块3a还将试卷要求转换成试卷容器，将N个试题要求分别转换成N个试题容器；

S3：服务器2内的物品虚拟标记模块3b将步骤S2得到的容器试卷转换成虚拟标记试卷，同时还将步骤S2得到的试卷容器转换成虚拟标记试卷容器，将步骤S2得到的N个试题容器分别转换成N个虚拟标记试题容器；

S4：服务器2内的本地虚拟标记模拟填充模块3c将步骤S1中设置的试卷属性填充至步骤S3得到的虚拟标记试卷容器中，得到完整虚拟标记试卷容器；本地虚拟标记模拟填充模块3c还将步骤S1中设置的N个试题属性分别对应填充至步骤S3得到的N个虚拟标记试题容器，得到N个完整虚拟标记试题容器；

S5：服务器2内的控制反转组卷模块3d将完整虚拟标记试卷容器的试卷虚拟标记及其试卷属性写入所述数据库4，控制反转组卷模块3d将N个完整虚拟标记试题容器的试题虚拟标记及其试题属性写入数据库4；

S6：服务器2根据步骤S5写入的所有数据在数据库4中查询所有试卷数据信息和所有试题数据信息；

S7：设定试卷调取原则和试题调取原则，服务器2内的控制反转组卷模块 3d根据试卷属性和试卷数据信息，在所述数据库4中调取与试卷属性对应的试卷数据至试卷容器中；同时控制反转组卷模块3d还根据所有试题属性和所有试题数据信息，在所述数据库4中调取与所有试题属性分别对应的试题数据至N 个试题容器中；

S8：将步骤S7得到的试卷数据、试题数据反馈至电子试卷输入输出平台，试卷数据、试题数据结合电子试卷框架得到电子试卷。

其中，步骤S6中所述的试卷数据信息为所述数据库4中包含的与试卷属性对应的所有试卷、试卷总数量和每个试卷的属性权值；所述试题数据信息为所述数据库4中包含的与所有试题属性分别对应的所有试题、试题数量和每个试题的属性权值。

其中，步骤S7中，采用贪心算法对所述数据库4中的试卷和试题进行调取。

其中，所述贪心算法对所述数据库4中试卷的试卷调取原则为：按照试卷的属性权值由高到低依次调取；所述贪心算法对所述数据库4中试题的试题调取原则为：按照试题的属性权值由高到低依次调取。

其中，步骤S6中查询到所述数据库4中不存在与试卷属性对应的试卷数据时，调整试卷属性至临近的试卷属性，进行试卷数据调取；步骤S6中查询到所述数据库4中不存在与试题属性对应的试题数据时，调整试题属性至临近的试题属性，进行试题数据调取。

在本发明中，令含有N+1个背包容器的容器试卷为集合S'，在集合S'中包含N+1个用于存储第i个属性的容器s_i，其中，i＝1,2,3…N,N+1，记为：>1,s₂,s₃…s_n,s_n+1}；则组卷过程中涉及N+1组属性。

在本发明中，通过减少数据库通信来提升制卷效率。首先通过一次数据库通信，获取数据库中保存的所有试题的信息，例如各类知识点题目的数量、难度等，返回至服务器，所需消耗的时间为：O(l)

在服务器中，根据制卷要求，认为设定每道试题的权值，作为贪心算法选择的依据，若有y道试题，则需消耗时间：O(y)

再根据贪心算法，对所有试题按权值进行排序后进行选择。假设每份试卷平均题数为在本实施例中，制卷要求为N+1个，则消耗的时间为：

若有m份试卷，则小号的时间为：

则本模块总时间复杂度为数据库通信的时间复杂度、加权值计算的时间复杂度、制m份卷贪心算法的时间复杂度与控制反转组卷模块将制成试卷存入数据库的时间复杂度之和：

化简得

因为数据库通信的时间远远大于CPU计算时间，即O(l)＞＞O(y)，则本发明时间复杂度可以简化为：O(l)

传统组卷算法时间复杂度简化为：

由于：

故本发明的时间复杂度远远小于传统组卷算法的时间复杂度。

控制反转组卷模块，通过试卷的约束条件在数据库中选取试题转化为通过虚拟容器中保存的相关属性进行数据库中题目的选取。使得数据库读取次数减少，提升程序运行效率。

应当指出的是，上述说明并非是对本发明的限制，本发明也并不仅限于上述举例，本技术领域的普通技术人员在本发明的实质范围内所做出的变化、改性、添加或替换，也应属于本发明的保护范围。