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
在遙遠的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團決定。陪審團是由法官從公眾中挑選的。先隨機挑選n 個人作為陪審團的候選人，然后再從這n 個人中選m 人組成陪審團。選m 人的辦法是：控方和辯方會根據(jù)對候選人的喜歡程度，給所有候選人打分，分值從0 到20。為了公平起見，法官選出陪審團的原則是：選出的m 個人，必須滿足辯方總分和控方總分的差的絕對值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對值相同，那么選辯控雙方總分之和最大的方案即可。最終選出的方案稱為陪審團方案。
為敘述問題方便，現(xiàn)將任一選擇方案中，辯方總分和控方總分之差簡稱為“辯控差”，辯方總分和控方總分之和稱為“辯控和”。第i 個候選人的辯方總分和控方總分之差記為V(i)，辯方總分和控方總分之和記為S(i)。現(xiàn)用f(j, k)表示，取j 個候選人，使其辯控差為k 的所有方案中，辯控和最大的那個方案（該方案稱為“方案f(j, k)”）的辯控和。并且，我們還規(guī)定，如果沒法選j 個人，使其辯控差為k，那么f(j, k)的值就為-1，也稱方案f(j, k)不可行。本題是要求選出m 個人，那么，如果對k 的所有可能的取值，求出了所有的f(m, k) (-20×m≤ k ≤ 20×m)，那么陪審團方案自然就很容易找到了。
問題的關(guān)鍵是建立遞推關(guān)系。需要從哪些已知條件出發(fā)，才能求出f(j, k)呢？顯然，方案f(j, k)是由某個可行的方案f(j-1, x)( -20×m ≤ x ≤ 20×m)演化而來的。可行方案f(j-1, x)能演化成方案f(j, k)的必要條件是：存在某個候選人i，i 在方案f(j-1, x)中沒有被選上，且x+V(i) = k。在所有滿足該必要條件的f(j-1, x)中，選出 f(j-1, x) + S(i) 的值最大的那個，那么方案f(j-1, x)再加上候選人i，就演變成了方案 f(j, k)。這中間需要將一個方案都選了哪些人都記錄下來。不妨將方案f(j, k)中最后選的那個候選人的編號，記在二維數(shù)組的元素path[j][k]中。那么方案f(j, k)的倒數(shù)第二個人選的編號，就是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ù)組f 來存放f(j, k)的值。而且，由于題目中辯控差的值k 可以為負數(shù)，而程序中數(shù)租下標不能為負數(shù)，所以，在程序中不妨將辯控差的值都加上400，以免下標為負數(shù)導(dǎo)致出錯，即題目描述中，如果辯控差為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;
}