uva 562 - Dividing coins(01背包）

  題目大意：給出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;  
}