UVA Coin Change(674)

题目大意：

      将一对硬币分成两份，使得两份的总金额差最小。比如有三枚硬币，价值分别为2,3和5，则分成的两堆就是2,3一堆和 5一堆，它们的总金额差为0。

 

思路：

      属于动态规划问题，刚开始看，想到了最大连续子序列和的问题，但又有点不一样。后来发现得用0-1背包来解决。定义一个数组dp[Max]， Max要大一些，表示提供的硬币所能组成的所有和，dp[i]=1表示提供的硬币能够凑成 i ， dp[i]=0表示凑不成 i ， 这样从sum/2往下找，找到最大的，就是这些硬币所能凑成的总和最接近于sum/2的。

 

代码如下：

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	freopen( "test.txt", "r", stdin );

	int n, m, sum = 0, value, finalsum;
	vector<int> v;
	int T = 0;
	cin>>T;
	while( T-- )
	{
		cin>>m;
		for( int i = 0; i < m; i++ )
		{
			cin>>value;
			v.push_back(value);
			sum += value;
		}
		
		vector<int> dp(555555);
		dp[0] = 1;  

		for( int i = 0; i < m; i++ )
		{
			for( int j = sum; j>=v[i]; j-- )
			{
				if( dp[j - v[i]] )    //若v[i]=2，则当j=2时，dp[0]=1，说明2能够由一个价值为2的硬币凑成。
					dp[j] = 1;
			}
		}
		int tag = 0;
		for( int i = sum/2; i >= 0; i-- )
		{
			if( dp[i] )
			{
				tag = i;
				break;
			}
		}
		cout<<sum-2*tag<<endl;

		sum = 0;
		v.clear();
	}

	return 0;
}