链接:
https://www.acwing.com/problem/content/282/
题意:
在一个遥远的国家，一名嫌疑犯是否有罪需要由陪审团来决定。
陪审团是由法官从公民中挑选的。
法官先随机挑选N个人（编号1,2…,N）作为陪审团的候选人，然后再从这N个人中按照下列方法选出M人组成陪审团。
首先，参与诉讼的控方和辩方会给所有候选人打分，分值在0到20之间。
第 i 个人的得分分别记为p[i]和d[i]。
为了公平起见，法官选出的M个人必须满足：辩方总分D和控方总分P的差的绝对值|D-P|最小。
如果选择方法不唯一，那么再从中选择辨控双方总分之和D+P最大的方案。
求最终的陪审团获得的辩方总分D、控方总分P，以及陪审团人选的编号。
思路:
看不太懂题解..考虑二维背包, 选的人数第一维, 辩控差为第二维.
代码:
#include <bits/stdc++.h>
using namespace std;
int Dp[30][1000];
vector<int> Path[210][1000];
int p[210], d[210], sub[210], add[210];
int id[210];
int n, m;
int main()
{
int cnt = 0;
while (~scanf("%d%d", &n, &m))
{
if (n == 0 || m == 0)
break;
memset(Dp, -1, sizeof(Dp));
for (int i = 0;i < m;i++)
{
for (int j = 0;j < 1010;j++)
Path[i][j].clear();
}
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &p[i], &d[i]);
sub[i] = p[i] - d[i];
add[i] = p[i] + d[i];
}
int fix = m * 20;
Dp[0][fix] = 0;
for (int i = 1;i <= n;i++)
{
for (int j = m-1;j >= 0;--j)
{
for (int k = 0;k < 2*fix;k++)
{
if (Dp[j][k] >= 0 && Dp[j+1][k+sub[i]] <= Dp[j][k]+add[i])
{
Dp[j+1][k+sub[i]] = Dp[j][k]+add[i];
Path[j+1][k+sub[i]] = Path[j][k];
Path[j+1][k+sub[i]].push_back(i);
}
}
}
}
int k;
for (k = 0; k <= fix; k++)
{
if (Dp[m][fix - k] >= 0 || Dp[m][fix + k] >= 0)
break;
}
int div;
if (Dp[m][fix - k] > Dp[m][fix + k])
div = fix - k;
else
div = fix + k;
printf("Jury #%d\n", ++cnt);
printf("Best jury has value %d for prosecution and value %d for defence:\n", (div + Dp[m][div] - fix) / 2,
(Dp[m][div] - div + fix) / 2);
for (int i = 0;i < m;i++)
printf(" %d", Path[m][div][i]);
puts("");puts("");
}
return 0;
}