toj_2821_2.cpp

Tianjin University Online Judge 的80多道题目 .

/*2821.   Grouping Problem Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 288   Accepted Runs: 157


This is a short problem. However, short doesn't mean easy. You should think about it carefully.

N students are going to play the game of "Tug of War", which both you and me are familiar with. N people must be divided into two teams, and each person must be on one team or the other. For the reason of being fair, the difference of total weights of the two teams should be as nearly equal as possible.

Input
There are multiple test cases. The first line of each test case contains a single integer N (2 ≤ N ≤ 15). It is followed by a line with N integers indicating the weight of the N students. The weight is at least 80, and at most 400.

A line with a single zero indicates the end of the input.

Output
For each case, just print a line with a non-negative integer D, which is the smallest difference of the total weights of the two teams.
Sample Input

3
85
100
200
5
100
200
205
100
205
0

Sample Output

15
0

Problem Setter: Venice


Source: TJU Programming Contest 2007*/
#include<cstdio>
#include<cstdlib>
#include<cstring>

int main()
{
  int position , n , i , j , choice [ 20 ] , weight[ 20 ] , totalWeight , partWeight , diff , min;
//  freopen( "toj_2821_in.txt" , "r" , stdin );
  while ( scanf( "%d" , &n ) && n )
    {
      for( totalWeight = 0 , i = 0; i < n; i++ ){
	scanf( "%d" , &weight[ i ] );
	totalWeight+= weight[ i ] ;
      }
      memset( choice ,  0 , sizeof( int ) * n );
      position = 0;
      partWeight = 0;
      min = 0x7fffffff;
      while ( position < n )
	{
	  //	  for( partWeight = 0 , i = 0; i < n; i++ )
	  //	    partWeight += choice[ i ] * weight[ i ];
	  diff = abs( totalWeight - 2 * partWeight );
	  if ( diff < min )
	    min = diff;
	  choice[ 0 ]++;
	  position = 0;
	  while ( choice[ position ] > 1 ){
	    partWeight -= weight[ position ];
	    choice[ position ] = 0;
	    position++;
	    choice[ position ] ++;
	    partWeight += weight[ position ];
	  }
	}
      printf( "%d\n" , min );
    }
  return 0;
}