题目：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; } 
   
  

?