寫了３個小時終于過了，這道題讓我進一步了解和掌握了動態(tài)規(guī)劃，呵呵:-)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define offset ((20*m))
int f[100][2000];
int path[100][2000];
int minu[400];
int plus[400];
int a[400];
int b[400];
int n,m;
#define max(a,b) ((a>b?a:b))
bool check(int i,int n,int m)
{
while(true)
{
if(i==path[n][m])
return true;
if(n==0)
break;
m-=minu[path[n][m]];
n-=1;
}
return false;
}
int record[1000];
int main()
{
int i,j,k;
int testcase=0;
while(scanf("%d%d",&n,&m))
{
testcase++;
memset(path,-1,sizeof(path));
memset(f,-1,sizeof(f));
if(n==0&&m==0)
break;
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
minu[i]=a[i]-b[i];
plus[i]=a[i]+b[i];
}
for(i=1;i<=n;i++)
{
if(plus[i]>=f[1][minu[i]+offset])
{
f[1][minu[i]+offset]=plus[i];
path[1][minu[i]+offset]=i;
}
}
for(i=1;i<m;i++)
{
for(j=0;j<=offset*2;j++)
{
for(k=1;k<=n;k++)
{
if(f[i][j]>=0)
{
if(!check(k,i,j))
{
if(f[i][j]+plus[k]>=f[i+1][j+minu[k]])
path[i+1][j+minu[k]]=k;
f[i+1][j+minu[k]]=max(f[i+1][j+minu[k]],f[i][j]+plus[k]);
}
}
}
}
}
int mark;
for(i=0;i<=20*m;i++)
{
if( f[m][20*m+i]!=-1 || f[m][20*m-i]!=-1 )
{
mark=20*m+i;
if(f[m][20*m+i]>=f[m][20*m-i])
{
mark=20*m+i;
}
if(f[m][20*m+i]<f[m][20*m-i])
{
mark=20*m-i;
}
break;
}
}
int t,tt;
t=m;
tt=mark;
for(i=1;i<=m;i++)
{
record[i]=path[t][tt];
t-=1;
tt-=minu[record[i]];
}
sort(record+1,record+1+m);
int suma=0;
int sumb=0;
for(i=1;i<=m;i++)
{
suma+=a[record[i]];
sumb+=b[record[i]];
}
printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n",testcase,suma,sumb );
for(i=1;i<=m;i++)
printf(" %d",record[i]);
printf("\n\n");
}
return 0;
}