文档介绍：陪审团的妥协——张法睿要求: 根据控辩双方对候选人的评价, 选出最能让双方接受的陪审团。步骤:1、 控辩双方分别对每个候选人打分 2、 从m(<=200)个候选人中选出n(<=20)个组成陪审团要求:1、 双方对陪审团成员评分的差应尽量小 2、 双方对陪审团成员评分的和应尽量大问题抽象给定正数m,n(m<=200,n<=20),和长度为m的两个数组p,d满足0<=p[i]<=20,0<=d[i]<=20求序列1..m的一个n长的子序列S,满足:1、 ∑p[Si]与∑d[Si]的差尽量小2、 在满足1的前提下 ∑p[Si]与∑d[Si]的和尽量大3、 当有多组解的时候,答任何一解都算对简单的解法遍历所有的陪审团组合对每个组合打分记录最合要求的组合简单解法的评价优点:代码短、省人力缺点:速度慢,时间复杂度为n*C(m,n) 大数据可能通不过,不适合acm的规则题目提示:Ifyoursolutionisbasedonaninefficientalgorithm,:epted,soitwasprobablymoredifficultthanmostteamsthought动态规划——我的解法动态规划的基础:局部最优整体最优整体最优:从M(给定)个候选人中选出N(给定)个,得分差为X(给定)的,得分和最高的组合局部最优:从m(m<=M)个候选人中选出n(n<=N)个,得分差为X(给定)的,得分和最高的组合动态规划考虑到问题的规模——选出的陪审团不超过20人,每人得分的范围是0到+20陪审团的得分差不超出【-400,+400】最多有801种可能解这道题:先用动态规划求出给定的得分差时,最高的得分和,然后枚举出最小的得分差。动态规划表三维数组:Map[i][j][k]第一维:参选人员索引含义:M个候选人中的前i个第二维:选出人数索引含义:选出j个第三维:得分差索引含义:控辩双方得分差为k数组元素:最优解决方案初始化1、将动态规划表中所有方案标记为“不存在”2、植入种子, 标记map[0][0][0]存在,方案为谁也不选,得分和为0递推假设从前m(给定)人中选出n(n<=m,n<=N)人,得分差为X(所有可能值)的最优方案(得分和最高)都已找出则:FORi:=0TON-1DO FORj:=min(X)TOmax(X)DOIF(map[m][i][j]+第m+1人)>map[m][i+1][j+diff[m+1]] THENmap[m][i+1][j+diff[m+1]]:=map[m][i][j]+第m+1人; //用已经存在的方案和第m+1个候选人组合新方案注:diff[m+1]是第m+1个候选人的得分差