【DP】줄다리기 경기

제목.

한 학교에서 줄다리기 시합을 하는데 모든 사람이 두 조로 나뉘어져 있다. 모든 사람은 그 중의 한 조에 있어야 한다. 두 조의 인원 차이가 1을 넘지 못하도록 요구하고 두 조 내의 모든 인체를 합쳐서 가능한 한 접근해야 한다.

입력

데이터를 입력한 첫 번째 줄은 n으로 줄다리기 경기에 참가한 총 인원수를 나타낸다. n<=100, 다음 n줄은 첫 번째부터 n번째 개인의 체중을 나타낸다. 모든 사람의 체중은 정수(1<=weight<=450)이다.

출력

출력 데이터는 두 개의 정수를 포함해야 한다. 각각 두 그룹의 모든 사람의 체중과 한 개의 빈칸으로 구분해야 한다.만약 이 두 수가 같지 않다면 작은 것을 앞에 놓고 출력하십시오.

샘플 가져오기

3 100 90 200

출력 예제

190 200

문제풀이의 방향

이 문제가 차지하는 공간은 3차원에 달하는 것 같지만 i는 i-1과만 관련이 있기 때문에 구체적으로 실현할 때 1차원을 생략할 수 있다.또한 조작할 때 j와 k의 범위(0<=j<=i/20<=k<=j*450)를 제어하는 데 주의해야 한다. 그렇지 않으면 시간을 초과할 수 있다.

주의

총 중량의 합을 2로 나누는 수를 세어야만 중간 범위를 정할 수 있다

절차는 다음과 같다.

#include
#include
using namespace std;
int n,a[1001],t,s,f[1001][1001];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	   scanf("%d",&a[i]);
	   s+=a[i];//    
	}
	t=s/2;
	f[0][0]=1;  
	  for(int i=1;i<=n;i++)
	  {
	  	for(int j=min(n/2,i-1);j>=0;j--)
	  	{
	  	   for(int k=0;k<=j*450;k++)//          450
	  		{
	  			if(f[j][k]) f[j+1][k+a[i]]=1;// j  k     
	  		}
	  	}
	  }
	  for(int i=0;1;i++)
	  {
	  	if(f[n/2][t+i])
	  	{//       
	  	    printf("%d %d",min(t+i,s-t-i),max(t+i,s-t-i));//      
	  		break;
	  	}
	  	if(f[n/2][t-i])
	  	{//       
	  		printf("%d %d",min(t+i,s-t+i),max(t+i,s-t+i));//      
	  		break;
	  	}
	  }
	return 0;
}