/*
给定辩控双方给每个人的打分p[i],d[i]，
dp[j][k]表示前i个人有j个被选定，选定的人的辩控双方打分差之和是k，此状态下的最大辩控双方和
按01背包做，体积一维是1，体积二维是辩控双方打分差，价值是辩控双方打分和
要求体积一维不得超过m，体积二维在体积一维=m的情况下最小
状态转移方程：dp[j][k]=max(dp[j][k],dp[j-1][k-(a[i]-b[i])]+a[i]+b[i])
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
struct node{
int a,b,sum,dif;
}p[205];
int dp[
22][
1000];
int main(){
int n,m,tt=
1;
while(scanf(
"%d%d",&n,&
m),n){
memset(dp,-
1,
sizeof dp);
vector<
int> path[
21][
801];
for(
int i=
1;i<=n;i++
){
scanf("%d%d",&p[i].a,&
p[i].b);
p[i].sum=p[i].a+
p[i].b;
p[i].dif=p[i].a-
p[i].b;
}
int max_diff=m*
20;
//由于两者之差可能是负数，所以在所有差值上增加一个max_diff
dp[0][max_diff]=
0;
for(
int i=
1;i<=n;i++
)
for(
int j=m;j>=
1;j--)
//逆序枚举，保证每个候选人最多被选一次
for(
int k=
0;k<=max_diff*
2;k++
)
if(dp[j-
1][k]>=
0)
if(dp[j-
1][k]+p[i].sum>dp[j][k+
p[i].dif]){
dp[j][k+p[i].dif]=dp[j-
1][k]+
p[i].sum;
path[j][k+p[i].dif]=path[j-
1][k];
path[j][k+
p[i].dif].push_back(i);
}
int i,min_diff;
for(i=
0;i<=max_diff;i++
)
if(dp[m][max_diff-i]>=
0||dp[m][max_diff+i]>=
0)
break;
//找到最小的差 i
if(dp[m][max_diff-i]>dp[m][max_diff+i]) min_diff=max_diff-
i;
else min_diff=max_diff+
i;
cout << (dp[m][min_diff]+i)/
2 <<
" " <<(dp[m][min_diff]-i)/
2 <<
endl;
for(
int i=
0;i<m;i++
)
cout << path[m][min_diff][i] <<
" ";
puts(" ");
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10219236.html
