思路 01背包求方案数再除以2

1. $1 \sim N$的整数集合是个等差数列，所以累加和是确定的$\frac {(1+N)\*N} 2$。要求划分为两子集且和相等，故子集之和应该为数列累加和的一半，即$\frac {(1+N)\*N} 4$
   • 这里注意，只有当累加和为偶数时才能分成符合要求的两半，如果是奇数对半分会多出小数位，而子集是整数集合，显然凑不出来小数。所以，当计算出累加和为奇数时，直接输出0即可（WA了才反应过来。。）
2. 题目转化为“有$N$个物品，其价值分别为$1 \sim N$，每个物品只能使用1次，求‘考虑所有物品且总价值恰好为$\frac {(1+N)\*N} 4$（子集和）’的选法方案总数”，01背包，背包容量为$\frac {(\ 1+N_{max}\ \ )\*N_{max}} 4$
   • $f(i,j)$表示只考虑前$i$个物品且总价值恰好为$j$的选法集合，属性：$Sum$
   • 状态计算：
     • 选 $f(i,j) = f(i-1, j-v)$
     • 不选 $f(i,j) = f(i-1, j)$
     • 综上 $f(i,j) = f(i-1, j) + f(i-1, j-v)$
   • 初始值$f(0,0)=1$，意为不使用任何物品且总价值为0的选法方案总数为1（什么都不选），其余状态初始化为0
3. 注意
   • 原题求的是划分方案数，每个划分方案，对应的是2个不同的子集，即2个能组成指定总和的方案，所以最终答案应为$\frac {f(n,m)} 2, 其中m=\frac {(1+N)\*N} 4$
   • 方案总数可能很大，会爆int

代码 二维

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n;
    static long[][] f = new long[40][820];

    public static void main(String[] args) {
        n = scanner.nextInt();
        int m = (1 + n) * n / 2;  // 等差数列求和公式
        if ((m & 1) == 1) {  // 累加和为奇数 必不能划分成两个符合题意的整数集合
            System.out.println(0);
            return;
        } else {
            m >>= 1;  // 累加和为偶数 则求出子集之和
        }
        f[0][0] = 1;  // 不适用任何物品且总价值有0的方案有1种（什么都不选）
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= i) {
                    f[i][j] += f[i - 1][j - i];
                }
            }
        }
        System.out.println(f[n][m] / 2);
    }
}

代码 一维空间优化

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n;
    static long[] f = new long[820];

    public static void main(String[] args) {
        n = scanner.nextInt();
        int m = (1 + n) * n / 2;
        if ((m & 1) == 1) {
            System.out.println(0);
            return;
        } else {
            m >>= 1;
        }
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= i; j--) {
                f[j] += f[j - i];
            }
        }
        System.out.println(f[m] / 2);
    }
}