poj1015 Jury Compromise

Jury Compromise

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 33638		Accepted: 9084		Special Judge

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 

中文：

描述

在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：

控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。

输入

输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意，1<=n<=200, 1<=m<=20 而且 m<=n。接下来的n行，每行表示一个候选人的信息，它包含2个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0

输出

对每组数据，先输出一行，表示答案所属的组号,如 'Jury #1', 'Jury #2', 等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。

样例输入

4 2 
1 2 
2 3 
4 1 
6 2 
0 0

只是一个记录。
详解可以看:
https://www.cnblogs.com/kuangbin/archive/2011/08/04/2126809.html

总而言之，就是把背包问题的 x轴作为人数，y轴作为差值，记录和值
从1到m，枚举每一个情况，遇到差值重合则取总和较大一组，最后在第m行中由中间开始遍历寻找最近的，也就是差值最小的值。、
有几个注意点：
1 用path[][] 记录路径，枚举时要回溯查找 是否已经用过某个人。
2 由于差值可能为负，数组下表不能为负，所以一个修正值 fix=20*m 保证正确性

#include<iostream>
#include<cmath>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=202;
int n,m;
int dp[21][801],path[21][801];
int a[maxn],b[maxn],s[maxn],d[maxn];
vector<int> ans;

bool select(int j,int k,int i)
{
    while(j>0 && path[j][k]!=i)
    {
        k-=d[path[j][k]];
        j--;
    }
    return j?false:true;
}

int main(void)
{
 //     freopen("input.txt","r",stdin);
    int time=0;
    while(cin>>n>>m&&n)
    {
        time++;
        memset(dp,-1,sizeof dp);
        memset(path,0,sizeof path);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            s[i]=a[i]+b[i];
            d[i]=a[i]-b[i];
        }
        int fix=m*20;
        //dp
        dp[0][fix]=0;
        for(int j=1; j<=m; j++)
        {
            for(int k=0; k<=2*fix; k++)
            {
                if(dp[j-1][k]>=0)
                {
                    for(int i=1; i<=n; i++)
                    {
                        if(dp[j][k+d[i]]<dp[j-1][k]+s[i])
                        {
                            if(select(j-1,k,i))
                            {
                                dp[j][k+d[i]]=dp[j-1][k]+s[i];
                                path[j][k+d[i]]=i;
                            }
                        }
                    }
                }
            }
        }
        //output
        int k;
        for(k=0; k<=fix; k++)
        {
            if(dp[m][fix-k]>=0||dp[m][fix+k]>=0)
                break;
        }
        int x=dp[m][fix-k]>dp[m][fix+k]?fix-k:fix+k;
        int ansa=(dp[m][x]+x-fix)/2;
        cout<<"Jury #"<<time<<endl;
        cout<<"Best jury has value "<<ansa<<" for prosecution and value "<<dp[m][x]-ansa<<" for defence: "<<endl;
        ans.clear();
        for(int i=m;i>0;i--)
        {
                  ans.push_back(path[i][x]);
              x-=d[path[i][x]];
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++)
        {
              cout<<' '<<ans[i];
        }
        cout<<endl<<endl;
    }
    return 0;
}