题目传送门：http://acm.timus.ru/problem.aspx?num=1005

题意是给出n个正整数，现在可以把这n个整数划任意分成两堆，求这两堆数字和的差最小的值。

解法1：暴力枚举

因为题中的n <= 20, 直接枚举所有的可能（选和不选）总数为2^20 = 10^6, 能在1s算出来。
使用二进制枚举所有的子集方法会比dfs暴力标记容易。代码如下：

1
2
3
4
5
6
7
8
int ans = sum;
for (int j = 0; j < (1<<n); ++j) {
  int sum1 = 0;
  for (int i = 0; j >> i; ++i)
    if (1&(j>>i))
      sum1 += w[i];
  ans = min(ans, abs(2*sum1-sum));
}

解法2：DP动态规划

设第一堆的数字和为sum1, 所有数字总和为sum，则有
第二堆数字总和sum2 = sum-sum1, 求|sum1-sum2|最小值。

因为sum1和sum2是对称的，所以不妨设sum1 >= sum2, 则

1
2
|sum1-sum2| = sum1-(sum-sum1) = 2sum1-sum,
sum1 >= sum-sum1 => sum1 >= sum/2

题目问题转化为求2sum1-sum(sum1 >= sum/2)的最小值, 即0-1背包问题。

设dp[i][j]前i个数中组成的和能否j，1表示能，0表示不能，dp方程：dp[i][j] = dp[i-1][j] | dp[i-1][j-w[i]]

降成一维后：dp[j] = dp[j] | dp[j-w[i]], j从大到小枚举.

最后从i=sum/2递增开始查看dp[i]是否为真，为真则i为sum1的值，此时2*i-sum即是答案。

1
2
3
4
5
6
7
8
9
10
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 1; i <= n; ++i)
  for (int j = MAX-5; j >= w[i]; --j)
    dp[j] |= dp[j-w[i]];
for (int j = sum/2; j <= sum; ++j)
  if (dp[j] && 2*j >= sum) {
    cout << 2*j - sum << endl;
    break;
  }

贪心

这题很容易想到贪心方法方面去，贪心方法在这题上是不正确的，开始我想了一个贪心的算法：

  1. 排升序
  2. 取最大的一个作为sum1，第二大的一个作为sum2作为两堆
  3. 从第三大的数开始降序遍历，对每个遍历的数i，if sum1 < sum2, sum1+=i, otherwise sum2 += i
  4. 最后|sum1-sum2|

这个算法一开始我感觉是对的，试了很多例子都正确，可惜WA了。后来找到反例，最大和次最大有可能是在同一堆里！下面数据：

5
4 6 6 7 9

用贪心算法的同学，可以试试上面这组数据。