dp
本题为special judge，不需要考虑多解情况。
f[i][j]表示在选m个人中的选i个人的时候使所有已选中的人的p,d差为j时，所能获得的p,d最大和。
f[i + 1][j + p[k] - d[k]] = f[i][j] + p[k] + d[k];(要求k之前没有选过，要查看f[i][j]的完整路径，确保无k)
填写完成后，观察f[m]找到最小差值，最大和。知道和差自然可以求出总的p,d。
也可以用另一种方法：
三维f[i,j,k]表示前i取j差值为k的最大和
f[i,j,k]=max{f[i-1,j,k],f[i-1,j-1,k-s1[i]]+s2[i]}
我用的第一个：
/**
* Problem:POJ1015
* Author:Shun Yao
* Time:2013.6.2
* Result:Accepted
* Memo:DP
*/
#include <cstring>
#include <cstdio>
#include <algorithm>
long n, m, f[25][805], path[25][805], p[205], d[205], ans[205];
char vis[205];
int main() {
long i, j, k, t1, t2, tcase, w;
freopen("poj1015.in", "r", stdin);
freopen("poj1015.out", "w", stdout);
tcase = 0;
while (scanf("%ld%ld", &n, &m), n) {
w = m * 20;
for (i = 1; i <= n; ++i)
scanf("%ld%ld", p + i, d + i);
for (j = 0; j <= m; ++j) {
memset(f[j], 0xff, sizeof f[j]);
memset(path[j], 0, sizeof path[j]);
}
f[0][w] = 0;
for (j = 0; j < m; ++j)
for (k = 0; k <= (w << 1); ++k)
if (f[j][k] >= 0) {
memset(vis, 0, sizeof vis);
t1 = j;
t2 = k;
while (t1) {
vis[path[t1][t2]] = 1;
t2 -= p[path[t1][t2]] - d[path[t1][t2]];
--t1;
}
for (i = 1; i <= n; ++i)
if (!vis[i] && f[j + 1][k + p[i] - d[i]] < f[j][k] + p[i] + d[i]) {
f[j + 1][k + p[i] - d[i]] = f[j][k] + p[i] + d[i];
path[j + 1][k + p[i] - d[i]] = i;
}
}
i = w;
j = 0;
while (f[m][i - j] < 0 && f[m][i + j] < 0)
++j;
if (f[m][i - j] > f[m][i + j])
k = i - j;
else
k = i + j;
printf("Jury #%ld\n", ++tcase);
printf("Best jury has value %ld for prosecution and value %ld for defence:\n", (f[m][k] + k - w) >> 1, (f[m][k] - k + w) >> 1);
for (i = m; i >= 1; --i) {
ans[i] = path[i][k];
k -= p[ans[i]] - d[ans[i]];
}
std::sort(ans + 1, ans + m + 1);
for (i = 1; i <= m; ++i)
printf(" %ld", ans[i]);
puts("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}