5-6 无和集问题

问题描述

设 S 是正整数集合。 S 是一个无和集，当且仅当 x,y∈Sx,y∈S<script type="math/tex" id="MathJax-Element-1">x, y\in S</script> 蕴含x+y∉Sx+y∉S<script type="math/tex" id="MathJax-Element-2"> x + y \notin S</script> 。
对于任意正整数k，如果可将{1,2,...,k}{1,2,...,k}<script type="math/tex" id="MathJax-Element-3">\{1,2,...,k\}</script>划分为n个无和子集S1,S2,...,SnS1,S2,...,Sn<script type="math/tex" id="MathJax-Element-4">S_1,S_2,...,S_n</script> ，称正整数 k 是 n 可分的。记 F(n)=max{k|k是n可分的}F(n)=max{k|k是n可分的}<script type="math/tex" id="MathJax-Element-5">F(n)=max\{ k | k 是 n 可分的\}</script>。
试设计一个算法，对任意给定的 n ，计算F(n)F(n)<script type="math/tex" id="MathJax-Element-6"> F(n)</script> 的值。

对任意给定的 n ，编程计算 F(n)F(n)<script type="math/tex" id="MathJax-Element-7">F(n)</script> 的值。

数据输入：
第一行有 1 个正整数 n。

Java

package Chapter5HuiSuFa;

import java.util.Scanner;

public class WuHeJi {

    private static int n,k;
    private static long t0,t1;
    private static double elapsed;

    private static int MAX = 10000;
    private static int[][] sum;
    private static boolean[][] s;
    private static int[] t;

    private static int[] bestx;

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);

        while (true){
            k = 0;

            n = input.nextInt();

            s = new boolean[n+1][MAX];
            sum = new int[n+1][MAX];
            t = new int[MAX];
            bestx = new int[MAX];

            t0 = System.currentTimeMillis();

            search(1);

            System.out.println(k-1);
            for(int i=n; i>=1; i--){
                for(int j=1; j<=k-1; j++)
                    if(bestx[j] == i)
                        System.out.print(j+" ");
                System.out.println();
            }
        }
    }

    private static boolean search(int dep){
        if(dep >= k) {
            k = dep;
            for(int i=1; i<=k-1; i++)
                bestx[i] = t[i];
        }

        t1 = System.currentTimeMillis();
        elapsed += (t1-t0)/1000;
        t0 = t1;
        if(elapsed > 15.0) return false;

        if(dep > MAX)
            return true;

        for(int i=1; i<=n; i++){
            if(sum[i][dep] == 0){
                t[dep] = i;
                s[i][dep] = true;
                for(int j=1; j<dep; j++)
                    if(s[i][j])
                        sum[i][dep+j]++;
                if(search(dep+1))
                    return true;
                s[i][dep] = false;
                t[dep] = 0;
                for(int j=1; j<dep; j++)
                    if(s[i][j])
                        sum[i][dep+j]--;
            }
        }

        return false;
    }
}

Input & Output

2
8
1 2 4 8 
3 5 6 7 

3
23
1 2 4 8 11 16 22 
3 5 6 7 19 21 23 
9 10 12 13 14 15 17 18 20 

Reference

王晓东《计算机算法设计与分析》（第3版）P181