POJ1015 Jury Compromise

壮压DP

题目

Description

2000MS/65536K
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.

Simple input

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

Simple output

Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3

题目分析

题目大意： 在一个很随意的国家有一个很随意的选择陪审团的方式，控辩双方给每一个预备的陪审团成员打分，要求使得所有的控方和辩方打分的差值的绝对值最小，且控方打分和辩方打分之和最大的成员方案。

解题思路 ：动态规划
dp(i,j)表示辩控差为j的时候用i个候选人的取法中辩控和最大的那一种，dp(i,j)是由上一中dp(i-1,x)的状态下推演过来的，而这种条件成立的情况就是存在一个候选人y，y在dp(i-1,x)的情况下没有被选择上，而且x+v(i)=j;找出所有满足这种情况的i,并且将辩控和最大的保存在dp(i,j)中
路径的确定需要将中间的每一个人都记录下来，不妨将方案dp(j, k)中最后选的那个候选人的编号，记在二维数组的元素path[j][k]中。那么方案dp(j, k)的倒数第二个人选的编号，就是path[j-1][k-V[path[j][k]]]。
http://blog.csdn.net/lyy289065406/article/details/6671105

AC代码

83K/47MS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
void fre()
{
    freopen("c://test//input.in", "r", stdin);
    freopen("c://test//output.out", "w", stdout);
}
#define MP(x,y) make_pair(x,y)
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
#define debug puts("----------")
const long long mod = 1e9+7;
const int maxn = 1<<20;
const int inf = 0x3f3f3f3f;
using namespace std;
int n;  //候选人数
int m;  //当选人数
int dp[21][801];   //dp[j][k]：取j个候选人，使其辩控差为k的所有方案中，辩控和最大的方案的辩控和
int path[21][801];  //记录所选定的候选人的编号
///回溯确定在dp[j][k]方案中是否选过i人
bool select(int j,int k,int i,int* v)
{
    while(j>0 && path[j][k]!=i)
    {
        k-=v[path[j][k]];
        j--;
    }
    return j?false:true;
}

int main()
{
    int time = 1;
    while(cin>>n>>m&&n)
    {
        int j,k,i;
        int* p=new int[n+1];///控方值
        int* d=new int[n+1];///辩方值
        int* s=new int[n+1];///辩控和
        int* v=new int[n+1];///辩控差
        memset(dp,-1,sizeof(dp));
        memset(path,0,sizeof(path));
        for(i=1;i<=n;i++)
        {
            cin>>p[i]>>d[i];
            s[i]=p[i]+d[i];
            v[i]=p[i]-d[i];
        }
        int fix=m*20;
        dp[0][fix]=0;
        for(j=1;j<=m;j++)
        {
            for(k=0;k<=2*fix;k++)
            {
                if(dp[j-1][k]>=0)
                {
                    for(i=1;i<=n;i++)
                    {
                        if(dp[j][k+v[i]]<dp[j-1][k]+s[i])
                        {
                            if(select(j-1,k,i,v))
                            {
                                dp[j][k+v[i]]=dp[j-1][k]+s[i];
                                path[j][k+v[i]]=i;
                            }
                        }
                    }
                }
            }
        }
        for(k=0;k<=fix;k++)
            if(dp[m][fix-k]>=0||dp[m][fix+k]>=0)
            break;
        int di = dp[m][fix-k] > dp[m][fix+k] ? (fix-k):(fix+k);
        cout<<"Jury #"<<time++<<endl;
		cout<<"Best jury has value ";
		///辩方总值 = （辨控和+辨控差+修正值）/2
		cout<<(dp[m][di]+di-fix)/2<<" for prosecution and value ";
		///控方总值 = （辨控和-辨控差+修正值）/2
		cout<<(dp[m][di]-di+fix)/2<<" for defence:"<<endl;

		int* id=new int[m];
		for(i=0,j=m,k=di;i<m;i++)
		{
			id[i]=path[j][k];
			k-=v[ id[i] ];
			j--;
		}
		sort(id,id+m);   //升序输出候选人编号
		for(i=0;i<m;i++)
			cout<<' '<<id[i];
		cout<<endl<<endl;

		/*Relax*/

		delete p;
		delete d;
		delete s;
		delete v;
		delete id;
    }
}

题目链接

http://poj.org/problem?id=1015