Subset Sums - USACO 2.2.2

subsetsums - codetrick
For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.
For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:

• {3} and {1,2}

This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:

• {1,6,7} and {2,3,4,5}
• {2,5,7} and {1,3,4,6}
• {3,4,7} and {1,2,5,6}
• {1,2,4,7} and {3,5,6}

Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.
Your program must calculate the answer, not look it up from a table.

PROGRAM NAME: subset

INPUT FORMAT

The input file contains a single line with a single integer representing N, as above.

SAMPLE INPUT (file subset.in)

7  

OUTPUT FORMAT

The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition.

SAMPLE OUTPUT (file subset.out)

4

X.  http://www.boyu0.com/usaco-subset-sums/
http://www.cnblogs.com/ay27/archive/2012/10/31/2748292.html
http://jackneus.com/programming-archives/subset-sums/

此题目可以转化为，从小于N的所有数中，抽出任意个数字，使得它们的和等于所有数的和的一半，这很明显就是01背包问题了（具体参考楼教主的《背包九讲》）

然后分析题目，明显可以推论出来的是，当N个数字的总和为奇数时，此题不存在划分方案。
还有一个结论是，如果N个数字的和为偶数时，肯定存在划分方案，推论如下：

如果N为奇数，总是能够在[1,N-1]的数字中划分出(N-1)/2个相加等于N的数字对，而这个数字对个数肯定是奇数,因为两奇数相加等于偶数，三奇数相加等于奇数，所以N不可能为(1，5，9，13…)，即N可表示为（i*4）+3 ，i属于(0, 1, 2,…) ， （N-1)/2 = i*2+1，为奇数，。

如果N为偶数，总是能够在[1, N]中划分出N/2个相加等于N-1的数字对，这个数字对个数肯定是偶数，因为同理，N不可能为(2,6,10…)，即N可表示为(i*4）+ 4，i属于(0, 1, 2,…) ， N/2 = i*2+2, 为偶数。

然后我们还可以做一个优化，每次选择必选数字N，我们假设1到N的总和为count，这样问题就可以转化为：在1到N-1个数字当中，算出选出任意个数字使其的总和等于count-N的总方案数，很明显，这样我们节省了一半的组合可能性，可以使计算量大大减小，而且最后算出来的方案数就是原题目的解。

最后，状态转移方程为:

f[i][sum] = f[i-1][sum] + f[i-1][sum-i]

选取i个数字总和为sum的方案数等于选取i-1个数字总和为sum的方案数加上选取i-1个数字总和为sum-i的方案数
优化为一维数组的状态转移方程为

for i=0 .. N:
for j=sum..i:
f[j] += fun[j-i]

int main()

{

    FILE *fin  = fopen ("subset.in", "r");

    FILE *fout = fopen ("subset.out", "w");

    int sum;

    int i, j;

    fscanf(fin, "%d", &amp;n);

    sum = (n+1)*n/2;

    if(sum&amp;1)

    {

        fprintf(fout, "0\n");

        return 0;

    }

    

    sum &gt;&gt;= 1;

    sum -= n;

    

    dp[0] = 1;

    

    for(i=1;i<n;++i){

        for(j = sum;j>=i;--j){

            dp[j]+=dp[j-i];

        }

    }

    

    fprintf(fout, "%lld\n", dp[sum]);

    return 0;

}

Read full article from subsetsums - codetrick