uva562 - Dividing coins（01背包）

uva562 - Dividing coins（01背包）

題目：uva562 - Dividing coins（01背包）

題目大意：給出N個硬幣，每個硬幣有對應的面值。要求將這些硬幣分成兩部分，求這兩部分最小的差值。

解題思路：先求這些硬幣能夠湊出的錢（0， 1背包），然後再從sum（這些硬幣的總和）/2開始往下找這個值能否由這些硬幣湊出。要注意的是，可以由前n個硬幣組成那樣也是可以組成的面值。

代碼：

#include 
#include 

const int N = 105;
const int maxn = N * 500;

int v[N];
bool dp[maxn];
int n, sum;

void init () {

	memset (dp, false, sizeof (dp));
	dp[0] = true;

	for (int i = 0; i < n; i++)
		for (int j = sum; j >= v[i]; j--) {
				
			if (dp[j - v[i]])  
				dp[j] = true;
		//	dp[j] = dp[j - v[i]]; 這樣寫的話就否定了僅僅前面的i- 1個硬幣就組成j的情況。 
		}
}

int main () {

	int t;
	scanf (%d, &t);
	while (t--) {

		scanf (%d, &n);
		sum = 0;
		for (int i = 0; i < n; i++) {

			scanf (%d, &v[i]);
			sum += v[i];
		}
		
		init ();

		int i;
		for (i = sum / 2; i >= 0; i--) 
			if (dp[i])
				break;

		printf (%d
, sum - 2 * i);
				
	}
	return 0;
}