Tug of War

http://acm.pku.edu.cn/JudgeOnline/problem?id=2576

Description

A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

Input

The first line of input contains n the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 450. There are at most 100 people at the picnic.


Solving

집합 S에 속한 원소들을 반으로 나누려 한다. 이 때 나눠진 집합을 각각 A, B라 하면 A와 B에 속한 원소의 갯수의 차이는 1이하 (즉 S의 원소의 갯수가 짝수인 경우는 정확히 반으로 나누고 홀수인 경우 A나 B중 하나의 집합에 하나의 원소가 더 들어간다)여야 한다. 이 때 두 집합의 원소의 합의 차이가 최소가 되기를 원한다.

이 문제는 기본적으로 NP의 성격을 띄는 문제로 빠른 시간에 구할 수가 없으나 인풋 조건에서 원소의 갯수가 450개 원소의 값이 100이하로 주어진다. 따라서 원소의 총 합은 45000을 넘을 수가 없으므로 DP를 통해 문제를 해결할 수 있다. 그것도 간단한 DP로.

D[n][s] (n:사용한 원소의 갯수, s:사용한 원소로 만들 수 있는 총 합) 으로 공간을 정의하고
V[k]를 k번째 원소의 값으로 정의하면,

if (D[k-1][s] == true) D[k][s + V[k]] = true

와 같은 점화식을 얻을 수 있다.

아래의 코드는 위의 점화식에 실행속도를 향상시키기 위한 기법이 사용되었다.

#include <cstdlib> #include <cstdio> #include <memory> #include <cmath> #define min(a,b) (((a) < (b)) ? (a) : (b)) short C[51]; // i명의 사람으로 만들 수 있는 몸무게의 가지 수 short A[51][45001]; // i명의 사람으로 만들 수 있는 몸무게를 순서대로 저장 bool D[51][45001]; // i명의 사람으로 j의 몸무게를 만들 수 있는지 없는지 체크 int main() { int n, m; int i, j, k; int W[101]; int sum; int avg; while (scanf("%d", &n) > 0) { sum = 0; memset(D, 0x00, sizeof(D)); memset(W, 0x00, sizeof(W)); memset(C, 0x00, sizeof(C)); memset(A, 0x00, sizeof(A)); for (i = 0; i < n; i++) { scanf("%d", &W[i]); sum += W[i]; } avg = sum/2; m = n/2; for (i = 0; i < n; i++) { for (j = m-1; j >= 1; j--) { for (k = 0; k < C[j]; k++) { if (D[j+1][A[j][k] + W[i]] == false) { D[j+1][A[j][k] + W[i]] = true; A[j+1][C[j+1]++] = A[j][k] + W[i]; } } } if (D[1][W[i]] == false) { D[1][W[i]] = true; A[1][C[1]++] = W[i]; } } int minDist = 987654321; int minIndex = 0; for (i = 0; i < C[m]; i++) { if (abs(A[m][i] - avg) < minDist) { minDist = abs(A[m][i] - avg); minIndex = i; } } int les = min(A[m][minIndex], sum-A[m][minIndex]); int gre = sum - les; printf("%d %d\n", les, gre); } return 0; }