问题描述

设S是正整数集合。S是一个无和集，当且仅当x,y属于S，蕴含x+y不属于S。对于任意正整数k，如果可将{1，2，…，k}划分为n个无和子集S1，S2，…，Sn，则称正整数k是n可分的。记F(n)=max{k|k是n可分的}。试设计一个算法，对任意给定的n，计算F(n)的值。

输出输出示例

数据输入：第1行有1个正整数n。
结果输出：将计算的F(n)的值以及{1，2，…，F(n)}的一个n划分输出。第1行是F(n)的值。接下来n行，每行是一个无和子集Si。

输入：

2

输出：

8
1 2 4 8
3 5 6 7

算法分析

首先我们对问题进行解读，n表示我们最多只可以有n个子集。每个子集中任意的两个数的和不可以在这个子集中，反过来说也就是任意两个数之差不在这个集合里面。这里我们用深度优先策略的回溯法解决此问题。对于每一个新增的数，首先判断能不能加在子集中，如果能加在这个子集中有两个分支，一个是加在此子集，一个是判断能不能加在下一个子集。这里先判断加在子集中，然后就会判断下一个数能否加在子集中，一直判断到一个数不能加在所有子集中为止，然后回溯到上一个结点，恢复之前的条件，再判断上一个数能不能加在下一个子集，当当前的数不能加到所有的子集中时将当前值和最优值进行比较，如果当前值没有最优值好就剪掉。由此遍历所有可能出现的结果，最后输出最优解和最优值。（感觉我说的好啰嗦…）

代码

定义存储当前解的数组a[N][N],其中a[n][0]表示第n个子集的元素个数a[n][1]到a[n][a[n][0]]为这个子集的所有元素。定义n。设置初始的结果ans为1(最后要减1，所以初始值其实是0)，定义最优值为best，定义最优解为e[N][N]，其中的结构和a[N][N]一样,以及定义判定数组h[N][N]，h[i][j]表示第i个子集中是否有j这个元素。

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N][N], n, ans = 1, best, e[N][N];
bool h[N][N];

void dfs(int level){                        //判断当前ans中的数是否能插入第level个子集
    if(level == n){                         //n个子集的下标是0到n-1,所以当level等于n时表示当前ans不能插入所有子集
        if(ans <= best) return;             //如果当前ans不如当前最优值best，就返回
        best = ans;                         //如果比最优值好，更新最优值和最优解
        for(int i = 0; i < n; i ++){
            for(int j = 0; j <= a[i][0]; j ++)
                e[i][j] = a[i][j];
        }
        return;
    }
    else{                                   //判断ans能否插入第level个子集
        bool flag = true;           
        for(int i = 1; i <= a[level][0]; i ++){//遍历子集
            //如果ans减当前元素在子集中且这个元素不是它本身,flag就为false,表示ans不能插入这个子集
            if(h[level][ans - a[level][i]] && ans - a[level][i] != a[level][i]) flag = false;
        }
        if(!flag) dfs(level + 1);           //不能插入，判断ans能不能插入第level+1个子集  
        else{                               //可以插入，分两种情况，一种是插入，一种是不插入此子集
            //插入的情况
            a[level][++ a[level][0]] = ans; //第i个子集个数加一，把元素记入子集
            h[level][ans ++] = true;        //把此元素标记为在此子集中
            dfs(0);                         //判断下一个数是否能插入第0个子集
            //不插入的情况，把子集个数减1，再把当前元素标记为不在此子集中
            -- a[level][0];                 
            h[level][-- ans] = false;
            dfs(level + 1);                 //判断这个数是否能插入下一个子集
        }   
    }
}

int main()
{
    cin >> n;
    dfs(0);
    cout << --best << endl;                 //记录的是最优值加一，这里减去一并输出
     for(int i = 0; i < n; i ++){
            for(int j = 1; j <= e[i][0]; j ++)
                printf("%d ", e[i][j]);     //输出最优解
        puts("");
    }
    return 0;
}