[UVa] 10032 - Tug of War

題目網址: http://goo.gl/h6lfTF

題意: 給定n個人以及他們每個人的體重，要求將這n個人分成兩隊，且兩隊人數差不得超過1個人，且要使得兩個隊伍的體重和相差最小，輸出最後兩隊的體重和。



解法:  從某集合取出子集使得子集的和為某數，是常見的subset sum problem，由於子集合的人數是有限制的，所以遞迴方程要做個小改變。

dp[w] = p=
{ 1, if w = 0
{  dp[w-wi]<<1, if w > 0 and w >= wi, 1 <= i <= n
表示體重和為w時，有哪些可能的人數集合(p狀態壓縮)來形成w。

TAG: DP, subset sum, state compression

注意: 剛開始時就想到DP，只是被lucky cat誤導以為greedy可解，可惡。

程式碼:

	/* Tittle: 10032 - Tug of War
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/08
	* File: 10032 - Tug of War.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	typedef long long ll;
	// declarations
	int t;
	int n, ndiv2;
	int wei[N];
	ll dp[25000];
	int sum, sumdiv2;
	// functions
	// main function
	int main( void )
	{
	// input
	scanf( "%d", &t );
	while( t-- ) {
	scanf( "%d", &n );
	sum = 0;
	FOR( i, 1, n ) {
	scanf( "%d", &wei[i] );
	sum += wei[i];
	}
	sumdiv2 = sum/2;
	ndiv2 = n/2;
	// solve
	clr( dp, 0 );
	dp[0] = 1LL;
	FOR( i, 1, n ) for( int j=sumdiv2; j>=wei[i]; --j )
	dp[j] |= dp[j-wei[i]] << 1;
	// output
	int v;
	if( n&1 )
	for( v=sumdiv2; v>=0 && (dp[v]&(1LL<<ndiv2))==0 && (dp[v]&(1LL<<ndiv2+1))==0 ; --v );
	else
	for( v=sumdiv2; v>=0 && (dp[v]&(1LL<<ndiv2))==0; --v );
	printf( "%d %d\n", v, sum-v );
	if( t ) putchar('\n');
	}
	return 0;
	}

view raw 10032 - Tug of War.cpp hosted with ❤ by GitHub