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
在遙遠(yuǎn)的國(guó)家佛羅布尼亞，嫌犯是否有罪，須由陪審團(tuán)決定。陪審團(tuán)是由法官?gòu)墓娭刑暨x的。先隨機(jī)挑選n 個(gè)人作為陪審團(tuán)的候選人，然后再?gòu)倪@n 個(gè)人中選m 人組成陪審團(tuán)。選m 人的辦法是：控方和辯方會(huì)根據(jù)對(duì)候選人的喜歡程度，給所有候選人打分，分值從0 到20。為了公平起見(jiàn)，法官選出陪審團(tuán)的原則是：選出的m 個(gè)人，必須滿(mǎn)足辯方總分和控方總分的差的絕對(duì)值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對(duì)值相同，那么選辯控雙方總分之和最大的方案即可。最終選出的方案稱(chēng)為陪審團(tuán)方案。
為敘述問(wèn)題方便，現(xiàn)將任一選擇方案中，辯方總分和控方總分之差簡(jiǎn)稱(chēng)為“辯控差”，辯方總分和控方總分之和稱(chēng)為“辯控和”。第i 個(gè)候選人的辯方總分和控方總分之差記為V(i)，辯方總分和控方總分之和記為S(i)。現(xiàn)用f(j, k)表示，取j 個(gè)候選人，使其辯控差為k 的所有方案中，辯控和最大的那個(gè)方案（該方案稱(chēng)為“方案f(j, k)”）的辯控和。并且，我們還規(guī)定，如果沒(méi)法選j 個(gè)人，使其辯控差為k，那么f(j, k)的值就為-1，也稱(chēng)方案f(j, k)不可行。本題是要求選出m 個(gè)人，那么，如果對(duì)k 的所有可能的取值，求出了所有的f(m, k) (-20×m≤ k ≤ 20×m)，那么陪審團(tuán)方案自然就很容易找到了。
問(wèn)題的關(guān)鍵是建立遞推關(guān)系。需要從哪些已知條件出發(fā)，才能求出f(j, k)呢？顯然，方案f(j, k)是由某個(gè)可行的方案f(j-1, x)( -20×m ≤ x ≤ 20×m)演化而來(lái)的。可行方案f(j-1, x)能演化成方案f(j, k)的必要條件是：存在某個(gè)候選人i，i 在方案f(j-1, x)中沒(méi)有被選上，且x+V(i) = k。在所有滿(mǎn)足該必要條件的f(j-1, x)中，選出 f(j-1, x) + S(i) 的值最大的那個(gè)，那么方案f(j-1, x)再加上候選人i，就演變成了方案 f(j, k)。這中間需要將一個(gè)方案都選了哪些人都記錄下來(lái)。不妨將方案f(j, k)中最后選的那個(gè)候選人的編號(hào)，記在二維數(shù)組的元素path[j][k]中。那么方案f(j, k)的倒數(shù)第二個(gè)人選的編號(hào)，就是path[j-1][k-V[path[j][k]]。假定最后算出了解方案的辯控差是k，那么從path[m][k]出發(fā)，就能順藤摸瓜一步步求出所有被選中的候選人。初始條件，只能確定f(0, 0) = 0。由此出發(fā)，一步步自底向上遞推，就能求出所有的可行方案f(m, k)( -20×m ≤ k ≤ 20×m)。實(shí)際解題的時(shí)候，會(huì)用一個(gè)二維數(shù)組f 來(lái)存放f(j, k)的值。而且，由于題目中辯控差的值k 可以為負(fù)數(shù)，而程序中數(shù)租下標(biāo)不能為負(fù)數(shù)，所以，在程序中不妨將辯控差的值都加上400，以免下標(biāo)為負(fù)數(shù)導(dǎo)致出錯(cuò)，即題目描述中，如果辯控差為0，則在程序中辯控差為400。
#include <iostream>
using namespace std;
int p[201],d[201],result[21];
int dp[21][801],path[21][801];
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
bool select(int a,int b,int i){
while(a>0 && path[a][b]!=i){
b-=p[path[a][b]]-d[path[a][b]];
a--;
}
return (a!=0)?true:false;
}
int main(){
int i,j,k,a,b,n,m,origin,ca=1;
while(scanf("%d %d",&n,&m),n||m){
for(i=1;i<=n;i++)
scanf("%d %d",p+i,d+i);
memset(dp,-1,sizeof(dp));
memset(path,0,sizeof(path));
origin=m*20;
for(dp[0][origin]=j=0;j<m;j++)
for(k=0;k<=origin*2;k++)
if(dp[j][k]>=0){
for(i=1;i<=n;i++)
if(dp[j+1][k+p[i]-d[i]]<dp[j][k]+p[i]+d[i]){
a=j,b=k;
if(!select(a,b,i)){
dp[j+1][k+p[i]-d[i]]=dp[j][k]+p[i]+d[i];
path[j+1][k+p[i]-d[i]]=i;
}
}
}
for(i=origin,j=0;dp[m][i+j]<0 && dp[m][i-j]<0;j++);
k=dp[m][i+j]>dp[m][i-j]?i+j:i-j;
printf("Jury #%d\n",ca++);
printf("Best jury has value %d for prosecution and value %d for defence:\n",(dp[m][k]+k-origin)/2, (dp[m][k]-k+origin)/2);
for(i=1;i<=m;i++){
result[i]=path[m-i+1][k];
k-=p[result[i]]-d[result[i]];
}
qsort(result+1,m,sizeof(int),cmp);
for(i=1;i<=m;i++)
printf(" %d",result[i]);
printf("\n");
printf("\n");
}
return 0;
}