文档介绍：陪审团的妥协
——张法睿
要求: 根据控辩双方对候选人的评价, 选出最能让双方接受的陪审团。
步骤: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的规则
题目提示:
If your solution is based on an inefficient algorithm,
it may not execute in the allotted time.
当年裁判的笔记:
This problem was often submitted but never accepted,
so it was probably more difficult than most teams thought
动态规划
——我的解法
动态规划的基础:局部最优整体最优
整体最优:
从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(所有可能值)的最优方案(得分和最高)
都已找出
则:
FOR i:=0 TO N-1 DO
FOR j:=min(X) TO max(X) DO
IF (map[m][i][j]+第m+1人)>map[m][i+1][j+diff[m+1]]
THEN
map[m][i+1][j+diff[m+1]]:=
map[m][i][j]+第m+1人;
//用已经存在的方案和第m+1个候选人组合新方案
注:diff[m+1]是第m+1个候选人的得分差