280. 陪审团 poj1015（背包DP）

本文主要是介绍280. 陪审团 poj1015（背包DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在一个遥远的国家，一名嫌疑犯是否有罪需要由陪审团来决定。

陪审团是由法官从公民中挑选的。

法官先随机挑选N个人（编号1,2…,N）作为陪审团的候选人，然后再从这N个人中按照下列方法选出M人组成陪审团。

首先，参与诉讼的控方和辩方会给所有候选人打分，分值在0到20之间。

第 i 个人的得分分别记为p[i]和d[i]。

为了公平起见，法官选出的M个人必须满足：辩方总分D和控方总分P的差的绝对值|D-P|最小。

如果选择方法不唯一，那么再从中选择辨控双方总分之和D+P最大的方案。

求最终的陪审团获得的辩方总分D、控方总分P，以及陪审团人选的编号。

输入格式
输入包含多组测试数据。

每组测试数据第一行包含两个整数N和M。

接下来N行，每行包含两个整数p[i]和d[i]。

每组测试数据之间隔一个空行。

当输入数据N=0，M=0时，表示结束输入，该数据无需处理。

输出格式
对于每组数据，第一行输出’Jury #C’，C为数据编号，从1开始。

第二行输出“Best jury has value P for prosecution and value D for defence:”，P为控方总分，D为辩方总分。

第三行输出按升序排列的陪审人选编号，每个编号前输出一个空格。

每组数据输出完后，输出一个空行。

数据范围
1≤N≤200,
1≤M≤20
输入样例：
4 2
1 2
2 3
4 1
6 2
0 0
输出样例：
Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3

思路： dp(i,j)代表选了前i个数的时候，(p[i] - d[i])和为j的最大(p[i] + d[i])和。
再开一个路径数组path(x,i,j)记录到了第x个数，选了前i个数，(p[i] - d[i])和为j的时候，对应的编号。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;#define INF 0x3f3f3f3fconst int maxn = 205;
vector<int>ans;
int p[maxn],d[maxn];
int path[maxn][25][805],dp[25][805],suma,sumb;void dfs(int i,int j,int k)
{if(j == 0)return;int last = path[i][j][k];dfs(last - 1,j - 1,k - (p[last] - d[last]));ans.push_back(last);suma += p[last];sumb += d[last];
}int main()
{int n,m;int kase = 0;while(~scanf("%d%d",&n,&m) && n && m){for(int i = 1;i <= n;i++){scanf("%d %d",&p[i],&d[i]);}ans.clear();suma = 0;sumb = 0;memset(dp,-INF,sizeof(dp));dp[0][400] = 0;for(int i = 1;i <= n;i++){for(int j = 0;j <= m;j++)for(int k = 0;k <= 800;k++)path[i][j][k] = path[i - 1][j][k];for(int j = m;j > 0;j--)for(int k = 0;k <= 800;k++){if(k - (p[i] - d[i]) < 0 || k - (p[i] - d[i]) > 800)continue;if(dp[j][k] < dp[j - 1][k - (p[i] - d[i])] + (p[i] + d[i])){dp[j][k] = dp[j - 1][k - (p[i] - d[i])] + (p[i] + d[i]);path[i][j][k] = i;}}}int res = 0;for(int i = 0;i <= 400;i++){if(dp[m][400 + i] >= 0 && dp[m][400 + i] >= dp[m][400 - i]){res = 400 + i;break;}if(dp[m][400 - i] >= 0 && dp[m][400 - i] >= dp[m][400 + i]){res = 400 - i;break;}}dfs(n,m,res);printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n",++kase,suma,sumb);for(int i = 0;i < ans.size();i++){printf(" %d",ans[i]);}printf("\n\n");}return 0;
}