#include<stdio.h>
#include<algorithm>
#define max 99999

int t;
int isok[201][21];
int greata,greatb;


struct Node
{
	int number;
	int data;
};
Node a[200],b[200],minus[200],plus[200];
int sign[201][21];
int answer[21];
int cmp(const void * a,const void * b)
{
	struct Node * c=(struct Node *)a;
	struct Node * d=(struct Node *)b;
	if(c->data!=d->data)return c->data-d->data;
	else return c->number-d->number;
	
}
int cmp2(const void* a,const void* b)
{
	return *(int* )a-*(int *)b;
}
int fun(int i)//取绝对值
{
	if(i<0)return -i;
	else return i;
}

int dp(int n,int m)//这就是我的动态规划代码，麻烦大牛看看是否有问题啊，哪里 的问题啊
{
	if(isok[n][m]==1) return sign[n][m];
	int temp=0;
	if(m==0)
	{
		sign[n][m]=0;
		isok[n][m]=1;
			return 0;
	}
	if(n<m)
	{
		isok[n][m]=1;
		sign[n][m]=max;
		return sign[n][m];
		

	}
	
	if(n<0)return max;
		sign[n-1][m]=dp(n-1,m);
		sign[n-1][m-1]=dp(n-1,m-1);
	    isok[n-1][m]=1;
    	isok[n-1][m-1]=1;
	
		if(fun(sign[n-1][m])<fun(sign[n-1][m-1]+minus[n-1].data))
		{
			
			return sign[n-1][m];
		}
		else 
		{
		
			
			return sign[n-1][m-1]+minus[n-1].data;
		}
		
	
	
}

int main()
{
	int m,n;
	t=0;
	int t1;
	int t2;
	int round=1;
	greata=0;greatb=0;
	while(scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0)break;
	
		for(int i=0;i<n;i++)
		{
			minus[i].number=plus[i].number=b[i].number=a[i].number=i;
			scanf("%d%d",&a[i].data,&b[i].data);
			plus[i].data=a[i].data+b[i].data;
		
		}//输入的结果
		qsort(plus,n,sizeof(plus[0]),cmp);//按照和的从小到大排序
		for(int i=0;i<n;i++)
		{
			int number=plus[i].number;
			minus[i].data=a[number].data-b[number].data;
			minus[i].number=number;
		}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				{sign[i][j]=0;//记录数据
		isok[i][j]=-1;//记录是否已经搜索过了
		}
	
		t=dp(n,m);//这一步结果就不对了，哪位大牛帮忙看看啊，多谢了
	/////////下面不用看，上面错了
	
			t=0;
         for(int i=n,j=m;j>0;)
		{
			t1=dp(i-1,j);
			t2=dp(i-1,j-1);
			if(fun(t1)<fun(t2+minus[i-1].data))
			{
				i--;
			}
			else 
			{
				answer[t++]=minus[i-1].number;
				greata+=a[minus[i-1].number].data;
				greatb+=b[minus[i-1].number].data;
				j--;
				i--;
			}
		}
		printf("Jury #%d\n",round);
		printf("Best jury has value %d for prosecution and value %d for defence:\n",greata,greatb);
		qsort(answer,t,sizeof(int),cmp2);
		for(int i=0;i<t;i++)
		printf(" %d",answer[i]+1);
		printf("\n");
	}
}

• Re:哪位大牛帮看看啊，我的动态规划的子问题难道处理错了吗，多谢了 (11) tangbohu222 2011-03-21 19:38:34