範例程式碼 uva10032

//uva10032
#include<stdio.h>

int main(void) {
	int t, n, i, j;
	int A[100];
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n);
		int sum = 0;
		for(i = 0; i < n; i++)
			scanf("%d", &A[i]), sum+=A[i];
		int hsum = sum / 2, hn = n / 2;
		long long dp[hsum + 1];
		for(i = 0; i <= hsum; i++)
			dp[i] = 0;
		dp[0] = 1;
		for(i = 0; i < n; i++) {
			for(j = hsum; j >= A[i]; j--)
				dp[j] |= dp[j - A[i]] << 1LL;
		}
		if(n % 2)
			while(!(dp[hsum] & (1LL << hn)) && !(dp[hsum] & (1LL << (hn  +1))))
				hsum--;
		else
			while(!(dp[hsum] & (1LL << hn)))
				hsum--;

		printf("%d %d\n", hsum, sum - hsum);
		if(t)
			printf("\n");
	}
	return 0;
}