竞赛评卷地分配问的题目

《竞赛评卷地分配问的题目》由会员分享，可在线阅读，更多相关《竞赛评卷地分配问的题目（23页珍藏版）》请在装配图网上搜索。

1、word公平的竞赛评卷系统模型摘 要略关键词：简单二次加密算法 算法加密装箱法 离散整数规划模型 问题重述：略模型假设：基于此题采用简单二次加密算法，使其具有优良的某某性能，并基于DES的某某效果提出更好的加密方案2在评卷过程中，来自各个学校的评委之间不会彼此影响，即不会因为评委间的交流对评卷的公证性造成影响。3分配试卷过程中，对于评委“只允许的要求给与满足，对于评委的“要求评视为软要求，在满足其他条件的情况下尽量满足。4试卷的分配要达到的目标为：每个评委工作量差异很小，即评卷数量根本一致，每个评委评阅的试卷尽量广泛卷子来自学校数目尽量多。5每个评委只评一道题，即被编入一个题组便于管理，也减少

2、了评委的工作难度。，由于试卷按密码发放到不同题组，所以满足试卷发放的随机性，进一步保证公平性。模块一 试卷号的加密与解密1一种主流的数据加密算法 算法的加密过程： 使用 位密钥对 位数据块进展加密， 需要进展 轮编码。在每轮编码时， 一个 位的密钥值由 位的完整密钥通过置换得来，每轮编码过程中，64位数据与每轮密钥被输入一个称为的盒中， 由一个压码函数对数位进展编码。另外， 在每轮编码开始、过后以与每轮之间， 位数据被以一种特别的方式置换， 打乱数位顺序。在每一步处理中都要从 位的主密钥中得出一个唯一的轮次密钥。最后， 输入的 位原始数据被转换成 位看起来被完全打乱了的输出数据， 但可以用解密

3、算法将其转换成输入时的状态。 加密过程如如下图所示：图1除了DES，用于数据加密的还有MD5加密算法产生一个唯一的数字签名，仅用于加密。从这两种主流的加密算法来看，加密的根本思路为：通过一个不可逆的函数变换，最终得到从明码映射而来的密码。而加密的关键在于函数的选择，或者说是变换的复杂度。从前面的分析可知，加密的效果由两方面因素决定：1加密策略，如果加密策略不对外部公开，那么外部只有破解了这种策略才能破译，而破解的难度取决于加密策略的选择。2密钥的长度和复杂性。所谓密钥是指解密时参与运算要用到的一个特定的数据。2一个简单的数据加密方案考虑到本系统要处理的加密数据仅是一个4位的数码，DES等加密算

4、法并不适合处理如此短的数据加密，而且当数据长度很小时，DES也不能起到很好的加密效果，因此我们需要用一个简单的但无法通过局部数据得出公式的加密程式。简单二次加密算法本算法用到的两个加密函数：1按位循环加和函数FA：对于数码A：abcd，将c换为(c+d)模10，将b换为(b+c)模10，依次进展，最后将d换为(d+a)模10。2按位异或函数XORA，KK是加密者选定的与A等长的数码。输出结果为对A与K按位异或的结果。所谓二次加密就是用前面提到的第一个函数生成一个中间码，然后再用第二个函数生成密码。这样一个映射不是可以用简单的解析形式表示出来的，从几个对应的明码和密码中是无法找出其中的规律，进而

5、破译的。综上，在不公开加密算法的前提下可以起到很好的加密效果，完全可以满足系统需求。后附 算法源代码3一个基于DES的某某效果更好的加密方案从前述的简单加密模型中可以看出，在不知道加密策略的情况下，只能通过穷举法对数据进展破译，对于本系统的4位数码来说破译概率为1/10000。然而一旦加密策略被公开或是有人得知加密策略，密码只剩一层保护，即由加密者选定的数码K，此时仍只能穷举K值，破译率仍为1/10000。在这种情况下如果一份对应的明码与密码被得知，如此K值可被得到，密码将没有任何保护，密码的破译率为1。现在提出的算法解决如何在加密策略和局部明码对应密码被窃取后，其他密码仍不会被破译。前面已经

6、提到DES算法并不适合简单的4位数码的加密，由于数码只有4位，密钥K的长度也只能为4位。此时K的穷举空间只有2的4次方，显然这是很脆弱的。因此，提出下面的加密算法。掩码Y长度64位，每位取值为0或1，密钥K长度64位，每位取值0或1，数据明码D4位数码，密码M64位数码。掩码Y的作用是决定某位数据是否有效，即解密时通过掩码将无效位屏蔽掉。显然这里的Y应该有4位为1，其他位为0。（1） 对于明码D，通过掩码Y对无效位填充随机数码，得到64位码DY。（2） 对DY进展DES加密，K为密钥，最终得到一个64的密码。（3） 解密时按密钥K和掩码Y对密码进展解密得到原明码。此加密算法基于DES，因此它的

7、加密效果也更好，理论上破译可能很小，目前还只能通过计算机穷举，而DES实际密钥长度为56位，2的56次方的空间计算机要搜上千年，而掩码Y的穷举空间为C。这些都超过了解码的穷举空间10的4次方。综上可以说明这种加密算法是理论上最优的。模块二 试卷的分配数据分析：分析给出的XX赛区参赛情况表得到如下图：图2其中深蓝，浅蓝，黄色，棕色分别代表A，B，C，D题。从图中可以看出A，B题集中在1-19号学校，C,D题集中在20-35号学校，且A，B题总数量显著高于C，D。5号和14号学校有少量的，题。现在综合考虑一下要求，每份试卷经四位评委评阅，每位评委回避本校试卷，每个评委只评一类型题。那么我们可以假定

8、，对于号评委，如果他评的一道题目为类型，且学校的类型题数量不为，为满足要求，如此需其他位评委来评，也就是说类型题至少需位评委评阅。如果评类型题的所有评委所在学校都无题，如此最少需位评委评阅X类型题。现在考虑一个理想化的情况：对于评委分配到的题目数，即每位评委所评试卷数一样，份卷子来自个不同的学校满足广泛性，且均为同一类型题依题型将评委分组，而所有学校的卷子都没有剩余，并且卷子的分配满足了所有评委的特殊需求。每份试卷至少经过四位评委评阅。显然这是一个离散的整数优化问题。从数据中观察，试卷总数为份，而评委为名，来自不同学校。所以所有不可能全部一样。我们的优化目标应该是所有评委分配的试卷数量差的绝对

9、值最小，并且使份试卷来自的学校数最大。模型的建立与求解：由分析得此优化问题的数学描述：设x表示评委是否评第个学校的号题取值为或，表示评委是否评题为中的一题，为每份卷子的评阅次数，表示学校的号题是否为题取值为或。，；，；，取中的一题，n=1,2,3,4另外还有一些其他的评委特殊要求。后附源码问题分析到这里已经很清晰，但用求解发现，此问题的数据量很大，变量数目庞杂，运算的时间复杂度和空间复杂度惊人，存在数据溢出问题。因此应重新修改模型，以获得一个可行的解决方案。装箱法我们知道，问题最终的最优解是一个全局最优解。设试卷总量为，对于中一局部，如果不是非常接近，也就是说和相差一局部空间。那么的最优解也是

10、的解的一局部。此法称为装箱法，即缩小问题的空间和规模，将解的空间想象为一个箱子进展填充，以求缩小问题求解难度。综上修改后的模型可以表述为： 按照最优目标和要求对问题的解空间进展填充，将原问题转化为一个规模较小的问题； 通过前面的最优化模型对转化后的问题进展求解，得到该问题的解； 综合两局部解，得到最终的全局最优解。对装箱程序的一点解释：此程序要求输入，试卷的信息，并指定评委参加哪个题组，即评阅哪道题，。设题目有，；每道题的试卷数量为，试卷总量为，题目分到的评委为人，评委总数为人。如此应有，即评委分配比例近似一样。对于此题的数据，评题人，题人，题人，题人。在满足评委特殊要求的前提下，为达到最优，

11、还应尽量减少评委评到本校题目的可能性。仔细考虑一下，可以选择的方案并不多，可以通过枚举求得最优解。评委分配的一个初始表：题组评委号，22，15从所给数据和特殊要求可以看出，为达到最优解，可以调整的只能从评委喜好中做出牺牲，而且只能是将要求评，题的评委评题，取或，与评，题的评委交换学校只有，题且或数量小于学校的题数量。后附装箱法的程序源码模型求解： 先用装箱程序得到局部解：其中(sum M)：代表评委所评题目被表示为：，：代表学校的号卷子，M表示该评委分配到的卷子总数，没有卷子的为无评委学校，表示未能分配的卷子数，也就是待求解的剩下的局部问题，后面为剩下的题号：nkt表示m学校的编号为n的题，没

12、有被分配出的次数，k表示该题的类型,1=A，2=B，3=C，4=D。pingwei 1(sum 47):2:1 2:3 2:7 2:8 3:1 3:3 3:5 4:1 4:3 4:4 4:10 5:2 5:4 5:5 5:11 6:2 6:4 6:8 6:9 7:6 7:7 7:10 7:11 8:9 8:13 8:17 9:2 9:3 9:9 10:2 10:4 10:5 11:8 12:1 12:6 12:10 13:4 13:12 13:13 14:1 14:10 14:11 15:1 17:3 17:4 18:5 19:1pingwei 2(sum 47):1:2 1:6 1:9 1:

13、12 1:19 1:20 1:23 1:25 3:4 3:6 4:2 4:6 5:1 5:9 6:1 6:5 7:2 7:8 7:9 8:2 8:8 8:12 8:15 8:19 9:4 9:5 9:10 10:1 10:10 11:9 12:2 12:4 12:5 12:9 13:6 13:9 13:11 13:14 13:15 14:6 15:3 15:5 16:1 16:3 18:1 18:2 18:4pingwei 3(sum 46):5:14 5:15 14:12 14:15 20:3 20:4 20:5 20:7 21:2 21:3 21:5 21:6 21:7 21:8 22:4

14、 22:5 22:9 23:1 23:3 24:2 24:4 24:5 24:6 25:2 25:5 26:2 26:3 26:4 26:5 27:1 27:3 27:5 28:2 28:3 28:6 29:2 29:4 29:5 29:6 30:1 30:4 30:5 31:4 32:2 33:2 34:2pingwei 4(sum 47):1:1 1:4 1:5 1:11 1:18 1:21 1:27 2:1 2:3 2:7 2:8 3:1 3:3 3:5 5:2 5:4 5:11 6:2 6:4 6:6 7:6 7:7 7:11 8:1 8:14 8:17 9:2 9:6 10:2 10

15、:4 10:5 10:8 12:1 12:6 12:7 13:113:7 13:12 13:13 14:2 14:11 15:1 15:4 16:5 17:10 18:6 19:3pingwei 5(sum 47):1:3 1:7 1:10 1:14 1:22 1:23 1:24 1:28 2:4 2:5 2:6 3:2 3:4 3:6 6:3 6:7 7:4 7:8 7:9 8:11 8:12 8:15 8:16 8:20 9:5 9:10 10:1 10:3 11:5 11:10 12:3 12:5 12:8 13:5 13:8 13:10 13:14 13:15 14:3 14:7 15

16、:3 15:5 16:2 16:6 18:2 18:3 18:7pingwei 6(sum 47):1:1 1:4 1:8 1:11 1:13 1:18 1:21 1:26 1:30 2:1 2:3 2:7 2:8 3:1 3:3 3:5 4:1 4:3 4:10 5:4 5:5 7:3 7:5 7:6 8:1 8:4 8:17 9:3 9:6 10:4 10:8 11:3 11:4 12:6 12:7 12:1013:2 13:12 13:13 14:1 14:2 15:1 16:4 17:2 17:4 18:5 19:1pingwei 7(sum 47):1:6 1:9 1:12 1:16

17、 1:23 1:24 1:25 1:29 2:6 4:2 4:6 4:7 5:3 5:10 6:3 8:3 8:5 8:6 8:7 8:8 8:11 8:12 8:16 8:18 9:10 10:3 10:6 10:7 11:6 12:2 12:4 12:8 12:9 13:6 13:9 13:11 14:3 14:4 14:6 14:8 16:1 16:3 16:7 17:8 18:3 18:4 18:8pingwei 8(sum 46):5:14 5:15 14:12 14:15 20:3 20:4 20:5 20:7 21:2 21:3 21:5 21:6 21:7 21:8 22:4

18、22:5 22:9 23:1 23:3 24:2 24:4 24:5 24:6 25:2 25:5 26:2 26:3 26:4 26:5 27:1 27:3 27:5 28:2 28:3 28:6 29:2 29:4 29:5 29:6 30:1 30:4 30:5 31:4 32:2 33:2 34:2pingwei 9(sum 46):5:14 5:15 14:12 14:15 20:3 20:4 20:5 20:7 21:2 21:3 21:5 21:6 21:7 21:8 22:4 22:5 22:9 23:1 23:3 24:2 24:4 24:5 24:6 25:2 25:5 2

19、6:2 26:3 26:4 26:5 27:1 27:3 27:5 28:2 28:3 28:6 29:2 29:4 29:5 29:6 30:1 30:4 30:5 31:4 32:2 33:2 34:2pingwei 10(sum 47):1:7 1:10 1:14 1:19 1:24 1:25 1:28 2:2 3:2 4:6 4:7 4:9 5:9 6:1 6:5 7:1 7:8 7:9 8:2 8:3 8:5 8:6 8:15 8:19 11:1 11:2 11:5 11:6 11:9 11:10 12:2 12:3 13:5 13:8 13:10 13:14 14:4 14:6 1

20、4:7 14:9 16:2 16:6 16:7 17:8 18:4 18:7 19:2pingwei 11(sum 47):5:12 5:13 14:13 14:14 20:1 20:2 20:6 21:1 21:4 22:1 22:2 22:3 22:6 22:7 22:8 22:10 23:2 23:4 23:5 24:1 24:3 24:7 25:1 25:3 25:4 25:6 26:1 26:6 26:7 26:8 27:2 27:4 27:6 28:1 28:4 28:5 29:1 29:3 29:7 29:8 30:2 30:3 31:1 31:2 32:1 33:3 35:1p

21、ingwei 12(sum 47):1:4 1:5 1:11 1:13 1:15 1:26 1:27 2:1 2:3 4:1 4:3 4:4 5:4 5:5 5:6 6:2 6:6 6:8 6:9 6:10 7:3 7:5 7:10 7:11 8:4 8:10 9:2 9:3 9:7 10:5 10:8 11:3 11:7 13:1 13:2 13:313:4 13:13 14:1 14:2 14:5 16:5 17:1 17:10 18:5 18:6 19:3pingwei 13(sum 47):5:12 5:13 14:13 14:14 20:1 20:2 20:6 21:1 21:4 2

22、2:1 22:2 22:3 22:6 22:7 22:8 22:10 23:2 23:4 23:5 24:1 24:3 24:7 25:1 25:3 25:4 25:6 26:1 26:6 26:7 26:8 27:2 27:4 27:6 28:1 28:4 28:5 29:1 29:3 29:7 30:2 30:3 31:1 31:2 31:3 33:1 33:3 34:1pingwei 14(sum 47):1:1 1:5 1:8 1:13 1:15 1:17 1:27 1:30 4:1 4:3 4:5 4:8 5:5 5:6 5:7 5:8 6:4 6:8 6:9 6:10 7:3 7:

23、10 7:11 8:9 8:10 8:13 9:3 9:6 9:7 9:8 10:8 11:3 11:4 11:7 12:7 12:10 13:1 13:2 13:3 15:4 16:4 16:5 17:1 17:2 17:3 17:4 19:1pingwei 15(sum 46):5:14 5:15 14:12 14:15 20:3 20:4 20:5 20:7 21:2 21:3 21:5 21:6 21:7 21:8 22:4 22:5 22:9 23:1 23:3 24:2 24:4 24:5 24:6 25:2 25:5 26:2 26:3 26:4 26:5 27:1 27:3 2

24、7:5 28:2 28:3 28:6 29:2 29:4 29:5 29:6 30:1 30:4 30:5 31:4 32:2 33:2 34:2pingwei 16(sum 47):1:8 1:11 1:15 1:17 1:30 3:1 4:4 4:5 4:8 4:10 5:2 5:6 5:7 5:8 6:6 6:8 6:9 6:10 7:3 7:5 8:1 8:9 8:10 8:14 9:6 9:7 9:8 9:9 11:3 11:4 11:7 11:8 12:1 12:10 13:1 13:7 13:12 14:1 14:5 14:10 14:11 15:4 17:1 17:2 17:3

25、 17:4 17:10pingwei 17(sum 47):5:12 5:13 14:13 14:14 20:1 20:2 20:6 21:1 21:4 22:1 22:2 22:3 22:6 22:7 22:8 22:10 23:2 23:4 23:5 24:1 24:3 24:7 25:1 25:3 25:4 25:6 26:1 26:6 26:7 26:8 27:2 27:4 27:6 28:1 28:5 29:1 29:3 29:7 29:8 30:2 31:1 31:2 31:3 32:1 33:1 34:1 35:1pingwei 18(sum 0):pingwei 19(sum

26、0):pingwei 20(sum 47):1:13 1:17 1:18 1:21 1:26 1:27 1:30 2:7 2:8 4:4 4:5 4:8 4:10 5:2 5:6 5:7 5:8 5:11 7:5 7:7 7:10 8:4 8:13 8:14 8:17 9:2 9:7 9:8 9:9 10:2 11:8 12:1 12:6 12:7 13:2 13:3 13:4 13:7 14:5 14:10 15:4 16:4 16:5 17:1 17:2 17:3 19:3pingwei 21(sum 47):1:1 1:4 1:5 1:8 1:15 1:17 1:18 1:21 1:26

27、 3:3 3:5 4:5 4:8 5:7 5:8 5:11 6:2 6:4 6:6 6:10 7:6 7:7 8:1 8:4 8:9 8:10 8:13 8:14 9:8 9:9 10:2 10:4 10:5 11:4 11:7 11:813:3 13:4 13:7 14:2 14:5 14:10 14:11 15:1 16:4 18:5 18:6pingwei 22(sum 43):5:12 5:13 14:13 14:14 20:1 20:2 20:6 21:1 21:4 23:2 23:4 23:5 24:1 24:3 24:7 25:1 25:3 25:4 25:6 26:1 26:6

28、 26:7 26:8 27:2 27:4 27:6 28:1 28:4 28:5 29:1 29:3 29:7 29:8 30:2 30:3 31:1 31:2 31:3 32:1 33:1 33:3 34:1 35:1pingwei 23(sum 0):pingwei 24(sum 47):1:2 1:9 1:12 1:16 1:20 1:25 1:28 1:29 2:4 3:6 4:7 4:9 5:1 5:10 6:3 6:7 7:2 7:9 8:2 8:3 8:5 8:6 8:16 8:18 9:1 10:1 10:3 10:6 10:9 11:1 11:2 11:5 11:6 11:9

29、 11:1013:6 13:15 14:6 14:7 14:8 15:2 16:3 16:7 17:9 18:1 18:7 18:8pingwei 25(sum 0):pingwei 26(sum 47):1:3 1:10 1:14 1:19 1:22 1:28 1:29 2:2 2:5 4:2 4:9 5:1 5:3 6:1 6:5 7:1 7:4 7:8 8:2 8:3 8:7 8:8 8:18 8:19 8:20 10:3 10:6 10:7 10:9 11:1 11:2 11:5 11:6 11:9 11:1012:3 13:8 13:9 14:7 14:8 14:9 16:6 17:

30、8 17:9 18:1 18:8 19:2pingwei 27(sum 0):pingwei 28(sum 47):1:12 1:16 1:20 1:22 1:23 1:24 1:29 2:2 4:6 5:1 5:3 5:9 5:10 6:1 6:3 6:5 8:5 8:78:8 8:11 8:15 8:19 9:1 9:4 10:6 10:7 10:9 10:10 11:1 11:2 12:2 12:5 13:9 13:10 13:11 14:3 14:4 14:8 14:9 15:2 16:7 17:9 18:1 18:2 18:3 18:4 19:2pingwei 29(sum 47):

31、1:2 1:3 1:6 1:7 1:9 1:10 1:14 2:2 2:4 2:5 2:6 3:2 3:4 3:6 4:2 5:3 5:9 5:10 6:7 7:1 7:2 7:4 8:11 8:12 8:20 9:1 9:4 9:5 9:10 10:1 10:10 12:3 12:4 12:5 12:8 12:9 13:5 13:6 13:8 14:9 15:2 15:3 15:5 16:1 16:2 16:3 16:6pingwei 30(sum 47):1:2 1:3 1:6 1:7 1:16 1:19 1:20 1:22 2:4 2:5 2:6 3:2 3:4 4:7 4:9 6:7

32、7:1 7:2 7:48:6 8:7 8:16 8:18 8:20 9:1 9:4 9:5 10:7 10:9 10:10 12:4 12:8 12:9 13:5 13:10 13:11 13:14 13:15 14:3 14:4 15:2 15:3 15:5 16:1 16:2 17:8 17:9pingwei 31(sum 0):pingwei 32(sum 0):pingwei 33(sum 0):pingwei 34(sum 0):pingwei 35(sum 0):left:2517:10 (1)-118:2 (2)-118:3 (2)-118:6 (1)-118:7 (2)-118

33、:8 (2)-119:1 (1)-119:2 (2)-119:3 (1)-122:1 (3)-122:2 (3)-122:3 (3)-122:6 (3)-122:7 (3)-122:8 (3)-122:10 (3)-128:4 (3)-129:8 (3)-130:3 (3)-131:3 (3)-132:1 (3)-133:1 (3)-133:3 (3)-134:1 (3)-135:1 (3)-1对剩余的局部，采用前面提到的整数规划模型。得结果如下：对于C题：Pingwei 3：22:1 ，22:2 ，22:3Pingwei 8：22:6 ，22:7 ，22:8 Pingwei9：22:10 ，

34、28:4 ，29:8 Pingwei 22:30:3 ，31:3 ，32:1 ，33:1 ，33:3 ，34:1 ，35:1 C题的四位评委均分配到50份次试卷，显然对于C题已达到最优。对于A题：Pingwei 1：17：10 Pingwei 4：18：6Pingwei 6：19：1Pingwei 12：19：3对于B题：Pingwei 2：18：2Pingwei 5：18：3Pingwei 7：18：7Pingwei 10：18：8Pingwei 24：19：2模型的分析与检验：图3从上图可以看出，该模型的很好的解决了前面提出的试卷分配问题。并且该模型可以应用到更广泛的情形，而不仅仅是针对前

35、面的问题。模型的应用与评价：参考文献：附录：1 简单加密算法源代码C+实现：#include#include#include#define KEY 2451#define N 4int main() int i,j,mingma=0,mima=0,m,len;char mimaS10,mingmaS10; printf(da what:1 加密or 2 解密n); scanf(%d,&m); if(m=1) printf(input the numbern); scanf(%s,mingmaS); len = strlen(mingmaS);for(i=len-1;i0;i-) mimaSi-

36、1 = (mingmaSi+mingmaSi-1-0-0)%10+0; mingmaSi-1 = mimaSi-1; mimaSlen-1 = (mingmaS0+mingmaSlen-1-0-0)%10+0; mimaSlen=0; for(i=0;i=0;i-) mimaSi=mingma%10+0; mingma/=10; mimaSN=0; len = strlen(mimaS); mingmaSlen-1 = (mimaSlen-1-mimaS0+10)%10+0; mimaSlen-1 = mingmaSlen-1; for(i=0;i=0);for(pingwei(H):l1-s

37、um(schools(I):sum(number(J):for(type(K)|z(I,J,K)#eq#1:c(I,J,H)*py(H,K)=0);!回避本校;for(number(J):for(schools(I):for(pingwei(K)|I#eq#K:c(I,J,K)=0);!只评一道题;for(pingwei(I)|I#ne#18#and#I#ne#19#and#I#ne#23#and#I#ne#25#and#I#ne#27#and#I#ne#31#and#I#ne#32#and#I#ne#33#and#I#ne#34#and#I#ne#35:sum(type(J):py(I,J)

38、=1);!无评委学校;for(pingwei(I)| I#eq#18#or#I#eq#19#or#I#eq#23#or#I#eq#25#or#I#eq#27#or#I#eq#31#or#I#eq#32#or#I#eq#33#or#I#eq#34#or#I#eq#35:sum(type(J):py(I,J)=0);!评阅次数;for(schools(I)|I#ne#18#and#I#ne#19#and#I#ne#23#and#I#ne#25#and#I#ne#27#and#I#ne#31#and#I#ne#32#and#I#ne#33#and#I#ne#34#and#I#ne#35:for(nu

39、mber(J):sum(pingwei(K):c(I,J,K)=4);!评委的特殊要求;py(15,1)=0;py(15,2)=0;py(22,1)=0;py(22,2)=0;py(26,3)=0;py(26,4)=0;py(15,3)+py(15,4)=1;py(22,3)+py(22,4)=1;py(26,1)+py(26,2)=1;!0,1变量;for(schools(I):for(number(J):for(pingwei(K):bin(c(I,J,K);for(pingwei(I):for(type(J):bin(py(I,J);for(schools(I):for(number(J

40、):for(type(K):bin(z(I,J,K); 装箱法程序源码实现#include#include#define S 35 /学校编号#define N 30 /题目编号#define P 35 /评委编号#define T 4 /题目类型 A,B,C,D.#define TIMES 4 /评阅次数int main() int typeS+1N+1,chooseS+1N+1P+1=0,pTP+1,i,j,k;/数组 type 为输入的信息表,记录了每个学校每份卷子的题目类型(A,B,C,D),数组pT指定评委评哪道题,数组choose决定了每个学校每份卷子由哪些评委评阅 int sum

41、=0,nSumT+1=0,currentT+1=0,4,2,11,3,flag=0,s,cs; int pNP+1=0,min,l,h,fl,state,start,Average,pNo=0; /初始化 for(i=1;iS+1;i+) for(j=1;jN+1;j+) scanf(%d,&typeij); if(typeij!=0) sum+; nSumtypeij+; for(i=1;iP+1;i+) scanf(%d,&pTi); if(pTi!=0) pNo+; Average = (sum*TIMES)/pNo; printf(sum %d average %dn,sum,Aver

42、age); s= sum; sum=0; nSum1 = nSum1*4;nSum2 = nSum2*4; nSum3 = nSum3*4; nSum4 = nSum4*4;for(k=1;kTIMES+1;k+) sum+=s; for(i=1;iS+1;i+) for(j=1;jN+1;) if(typeij!=0) /约束 包括 回避本校，评委只评一题 /贪心选择，装箱，控制略小于接近average，以进展调整 if(chooseijcurrenttypeij!=1&typeij=pTcurrenttypeij&i!=currenttypeij&pNcurrenttypeijAverag

43、e) chooseijcurrenttypeij=1; pNcurrenttypeij+; min = pNcurrenttypeij; sum-; nSumtypeij-; /寻找下一个current flag=0; for(h=j+1;hN+1;h+) if(typeih!=0) flag=1; break; if(flag=0) cs = i+1; else cs = i; for(l=1;lpNl&l!=cs) min = pNl;currenttypeij = l; j+; fl=0; else if(fl=0) fl=1; state = currenttypeij; /检查是否进

44、入无法满足条件状态，并从此状态退出 else if(currenttypeij=state) fl=0; j+; for(start = 1;startP;start+) if(pT(currenttypeij+start)%(N+1)=typeij) currenttypeij = (currenttypeij+start)%(N+1); break; else j+; /分析结果输出 for(i=1;iP+1;i+) printf(pingwei %d(sum %d):n,i,pNi); for(j=1;jS+1;j+) for(k=1;kN+1;k+) if(choosejki=1) printf(%d:%d ,j,k); /printf(n); printf(n); printf(left:%dn,sum); for(i=1;iS+1;i+) for(j=1;jN+1;j+) if(typeij!=0) flag = 0; for(k=1;kP+1;k+) if(chooseijk=1) flag+; if(flag!=TIMES) printf(%d:%d (%d)-%dn,i,j,typeij,TIMES-flag); return 0;23 / 23