uva 562 - Dividing coins(01双肩包）

uva 562 - Dividing coins(01背包）

题目连接：562 - Dividing coins

题目大意：给出n个硬币的面值， 要求将这n个硬币分成两堆（不要求个数平均）， 尽量使得两堆硬币的和之差的绝对值最小， 病输出最小值的绝对值。

解题思路：将sum 总和的一半half看成是背包的容量， 然后进行01背包处理， 然后取尽量接近half的可达到值cur， half - cur 的两倍就是所要求的值ans， 注意一点， 当sum 为奇数的时候， ans 要加 1 。

#include <stdio.h>
#include <string.h>
const int N = 50005;
const int M = 105;

int n, sum, dp[N], coin[M], Max;

int solve() {
    memset(dp, 0, sizeof(dp));
    dp[0]= 1;
    int half = sum / 2;

    for (int i = 0; i < n; i++) {
	for (int j = half - 1; j >= 0; j--)
	    if (dp[j])	dp[j + coin[i]] = 1;
    }

    for (int i = 0; i <= half; i++)
	if (dp[half - i])   return i * 2;
}

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
	sum = 0;
	scanf("%d", &n);
	memset(coin, 0, sizeof(coin));
	for (int i = 0; i < n; i++) {
	    scanf("%d", &coin[i]);
	    sum += coin[i];
	}
	printf("%d\n", solve() + sum % 2);
    }
    return 0;
}