当前位置:首页 » Project Euler » 详细页

Special subset sums: optimum 题号:103 难度: 45 中英对照

Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

  1. S(B) ≠ S(C); that is, sums of subsets cannot be equal.
  2. If B contains more elements than C then S(B) > S(C).

If S(A) is minimised for a given n, we shall call it an optimum special sum set. The first five optimum special sum sets are given below.

n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}

It seems that for a given optimum set, A = {a1, a2, ... , an}, the next optimum set is of the form B = {b, a1+b, a2+b, ... ,an+b}, where b is the "middle" element on the previous row.

By applying this "rule" we would expect the optimum set for n = 6 to be A = {11, 17, 20, 22, 23, 24}, with S(A) = 117. However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for n = 6 is A = {11, 18, 19, 20, 22, 25}, with S(A) = 115 and corresponding set string: 111819202225.

Given that A is an optimum special sum set for n = 7, find its set string.

NOTE: This problem is related to Problem 105 and Problem 106.


Solution

首先根据题意,按照递推规则,取$n=6$时的集合中间较大的数$20$,可生成$n=7:A={20,31,38,39,40,42,45}$是符合条件的,此时$S(A)=128+127=255$。在此基础上最小化$S(A)$即可。 其次确定A的最小元素的最大值为$\left[ \frac{255}{7} \right]=36$,从而从小到大枚举$A$中的元素,其上限利用已枚举的元素进行限制。 对于已枚举的集合$A$,只需要判断其二元子集和三元子集的$S$值是否有重复即可(四元子集和五元子集恰好等于全集$A$减去二元子集和三元子集)。

Code

import java.util.HashSet;
public final class p103 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
    static public String run(){
        int a[]=new int[8];
        int min=255;
        String ans="20313839404245";
        for(a[1]=1;a[1]<=36;a[1]++){
            for(a[2]=a[1]+1;a[2]<=36;a[2]++){
                for(a[3]=a[2]+1;a[3]<a[1]+a[2];a[3]++){
                    for(a[4]=a[3]+1;a[4]<a[1]+a[2];a[4]++){
                        for(a[5]=a[4]+1;a[5]<a[1]+a[2]+a[3]-a[4];a[5]++){
                            for(a[6]=a[5]+1;a[6]<a[1]+a[2]+a[3]-a[5];a[6]++){
                                for(a[7]=a[6]+1;a[7]<a[1]+a[2]+a[3]+a[4]-a[5]-a[6];a[7]++){
                                    if(check(a)){
                                        int sum=0;
                                        for(int i=1;i<=7;i++) sum+=a[i];
                                        if(sum<min){
                                            min=sum;
                                            ans="";
                                            for(int i=1;i<=7;i++) ans+=a[i];
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
    static private boolean check(int a[]){
        HashSet<Integer> sum=new HashSet<Integer>();
        for(int i=1;i<=7;i++) for(int j=i+1;j<=7;j++){
            if(sum.contains(a[i]+a[j]))
                return false;
            sum.add(a[i]+a[j]);
        }
        for(int i=1;i<=7;i++) for(int j=i+1;j<=7;j++)for(int k=j+1;k<=7;k++){
            if(sum.contains(a[i]+a[j]+a[k]))
                return false;
            sum.add(a[i]+a[j]+a[k]);
        }
        return true;
    }
}
20313839404245
286ms