题目描述
对于很多由 1∼N 构成的连续整数集合,我们都可以将其划分为两个子集,并使得两个子集的和相等。
例如,当 N=3 时,我们可以将集合 {1,2,3} 划分为子集 {1,2} 和 {3},这也是唯一的一种满足条件的划分方式。
当 N=7 时,共有四种满足条件的划分方式,如下所示
{1,6,7} 和 {2,3,4,5}
{2,5,7} 和 {1,3,4,6}
{3,4,7} 和 {1,2,5,6}
{1,2,4,7} 和 {3,5,6}
现在,给定 N,请你计算将 1∼N 构成的连续整数集合划分为和相等的两个子集,共有多少种划分方式。
将一种划分方式的某个子集内部的元素之间进行顺序调整仍看作是同一种划分方式。
输入格式
共一行包含整数 N。
输出格式
输出一个整数,表示划分方案数。
如果无法划分,则输出 0。
数据范围
1≤N≤39
样例
输入样例:
7
输出样例:
4
算法1:DP——01背包问题
Java 代码
import java.util.*;
public class Main{
static int N = 40;
static long[][] f = new long[N][N * (N + 1) / 4];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = n * (n + 1) / 2;
if(m % 2 == 1){
System.out.println(0);
return;
}
m /= 2;
//初始化:前i个数中选出和为0的方案数只有1种(即不选)
for(int i = 0;i <= n;i++){
f[i][0] = 1;
}
for(int i = 1;i <= n;i++){
for(int j = 0;j <= m;j++){
f[i][j] = f[i - 1][j];
if(i <= j){
f[i][j] += f[i - 1][j - i];
}
}
}
System.out.println(f[n][m] / 2);
}
}
算法2:二进制枚举
Java 代码
import java.util.*;
public class Main{
static int N = 40;
static HashMap<Integer,Integer> map1 = new HashMap<>();
static HashMap<Integer,Integer> map2 = new HashMap<>();
static int[] a = new int[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = n * (n + 1) / 2;
if(m % 2 == 1){
System.out.println(0);
return;
}
m /= 2;
int mid = n / 2;
for(int i = 0;i < 1 << mid;i++){
int sum = 0;
for(int j = 0;j < mid;j++){
if((i >> j & 1) == 1){
sum += mid - j;
}
}
map1.put(sum,map1.getOrDefault(sum,0) + 1);
}
for(int i = 0;i < 1 << (n - mid);i++){
int sum = 0;
for(int j = 0;j < n - mid;j++){
if((i >> j & 1) == 1){
sum += n - j;
}
}
map2.put(sum,map2.getOrDefault(sum,0) + 1);
}
long res = 0;
for(Map.Entry<Integer,Integer> set : map2.entrySet()){
int k = m - set.getKey();
int cnt = set.getValue();
res += map1.getOrDefault(k,0) * cnt;
}
System.out.println(res / 2);
}
}
背包最后为什么要 /2
因为两个子集算作一种划分方式
背包模型~