Jury Compromise
Time Limit:1000MS Memory Limit:10000K
Total Submit:987 Accepted:246 Special Judged
Description
In Frobnia, a far-away country, the verdicts in court trials are determined by a jury consisting of members of the general public. Every time a trial is set to begin, a jury has to be selected, which is done as follows. First, several people are drawn randomly from the public. For each person in this pool, defence and prosecution assign a grade from 0 to 20 indicating their preference for this person. 0 means total dislike, 20 on the other hand means that this person is considered ideally suited for the jury.
Based on the grades of the two parties, the judge selects the jury. In order to ensure a fair trial, the tendencies of the jury to favour either defence or prosecution should be as balanced as possible. The jury therefore has to be chosen in a way that is satisfactory to both parties.
We will now make this more precise: given a pool of n potential jurors and two values di (the defence’s value) and pi (the prosecution’s value) for each potential juror i, you are to select a jury of m persons. If J is a subset of {1,…, n} with m elements, then D(J ) = sum(dk) k belong to J
and P(J) = sum(pk) k belong to J are the total values of this jury for defence and prosecution.
For an optimal jury J , the value |D(J) – P(J)| must be minimal. If there are several jurys with minimal |D(J) – P(J)|, one which maximizes D(J) + P(J) should be selected since the jury should be as ideal as possible for both parties.
You are to write a program that implements this jury selection process and chooses an optimal jury given a set of candidates.
Input
The input file contains several jury selection rounds. Each round starts with a line containing two integers n and m. n is the number of candidates and m the number of jury members.
These values will satisfy 1<=n<=200, 1<=m<=20 and of course m<=n. The following n lines contain the two integers pi and di for i = 1,...,n. A blank line separates each round from the next.
The file ends with a round that has n = m = 0.
Output
For each round output a line containing the number of the jury selection round ('Jury #1', 'Jury #2', etc.).
On the next line print the values D(J ) and P (J ) of your jury as shown below and on another line print the numbers of the m chosen candidates in ascending order. Output a blank before each individual candidate number.
Output an empty line after each test case.
Sample Input
4 2
1 2
2 3
4 1
6 2
0 0
Sample Output
Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3
Hint
If your solution is based on an inefficient algorithm, it may not execute in the allotted time.
Source
Southwestern European Regional Contest 1996
January 6th, 2006 11:01:27
抽象：
给定正数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、 当有多组解的时候，答任何一解都算对
January 6th, 2006 11:02:02
简单的解法：
遍历所有的陪审团组合
对每个组合打分
记录最合要求的组合
January 6th, 2006 11:03:18
动态规划：
动态规划的基础：局部最优?整体最优
整体最优：
从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个候选人的得分差
应选出的方案是
使map[M][N][i]存在,且i的绝对值最小的map[M][N][i]
如果map[M][N][+i] 和map[M][N][-i]都存在，
则选取两者中得分和较大的一个。
1、动态规划表的压缩存储
map[m][x][y]只在生成map[m+1][x][y]时有用
所以动态规划表中只用保留
第一维索引为m和m+1的数据
2、方案的存储
一个方案包括两个属性
1、候选人名单
2、得分和
当M=200时
候选人名单使用位集存储，
占用224bit(7个无符号长整形)
动态规划表占用的空间:2*21*801*8=269136字节(263k)
January 6th, 2006 11:04:54
然后贴一个鬼佬的思路：
Hi, I soved this problem. The program ran about 0.422 sec and used 768 kb , but there are people who solved it 0.050 – 0.110.How is it possible? do=0 for which (A[n][j] or A[n][-j]) == true is the minimum value for |s1|.
Here is my solution:
Let diff[i]=d[i]-p[i], sum[i]=d[i]+p[i], then the problem is to choose numbers p[1]..p[m] :
p[i] belongs 1..n
p[i]<>p[j] for i<>j;
(s1=diff[p[1]]+diff[p[2]]+…diff[p[m]])==min;
And when there are many numbers that minimize |s1| , then choose the one which maximizes s2=sum[p[1]]+sum[p[2]]+..sum[p[m]].
I used such DP interpretation:
It’s trivial to solve the problem for m=1.
If there is a solution for m=k, then we can build the solution for m=k+1 using procedure:
Let the solution for m=k be saved in an array A[i][j], where A[i][j] shows whether it’s possible to choose k candidates from the first i candidates that s1=j, and if it’s possible then C[i][j] shows s2.
Then we can build an arrays B[i][j], D[i][j] for k+1 (which have the same function as A[i][j], C[i][j] for k):
Code:
for i=1 to n do
for j=< minimum possible sum> to
{
B[i][j]=B[i-1][j]; // do not include candidate number i
D[i][j]=D[i-1][j];
if(A[i][j-diff[i]])
if( (not B[i][j]) or (D[i][j]
To get chosen candidates, on each stage save whether a candidate was included or not.
Then just make a recursion descent.
I very accuratly implemented the algorithm ( using binary array to save whether a candidate was included or not), but the program is very slow.
Is it due to algorithm or implementation?