Subset Sums（DP）

Subset Sums
JRM

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

 

    题意：

    给出 N （1 ~ 39），说明有一个集合里面的数由 1 ~ N 组成，现将这一集合平均分成均等和的两份，问有几种分发。

 

    思路：

    DP。设dp[ i ] [ j ] 为当决定第 i 种选或者不选的时候刚好装满和为 j 时的方法数，那么若第 i 件物品选的话，那就是 dp [ i - 1 ] [ j - i ]，如果不选的话那就是dp[ i - 1 ] [ j ]。

    故当  j >= i  时  dp[ i - 1] [ j - i ] + dp[ i - 1 ] [ j ] = dp[ i ] [ j ]；

    当 j < i 时，dp [ i - 1] [ j ] = dp[ i ] [ j ]；

    注意方法数要开 long long 即可。

   

   AC：

/*    
TASK:subset    
LANG:C++    
ID:sum-g1    
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int main()
{
    freopen("subset.in","r",stdin);        
    freopen("subset.out","w",stdout);
    int n,sum = 0;
    long long dp[40][1000];
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        sum += i;
    if(sum % 2) printf("0\n");
    else
    {
        sum /= 2;
        for(int i = 0;i <= n;i++)
            dp[i][0] = 1;
//N内数构成和为0的方法就是全都不选，故只有1一种方法
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= sum;j++)
                if(j >= i)   dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i];
                else         dp[i][j] = dp[i - 1][j];
        printf("%lld\n",dp[n][sum] / 2);
    }
    return 0;
}