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:
- S(B) ≠ S(C); that is, sums of subsets cannot be equal.
- 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.
记S(A)是大小为n的集合A中所有元素的和。若任取A的任意两个非空且不相交的子集B和C都满足下列条件，我们称A是一个特殊的和集：
- S(B) ≠ S(C)；也就是说，任意子集的和不相同。
- 如果B中的元素比C多，则S(B) > S(C)。
对于给定的n，我们称使得S(A)最小的集合A为最优特殊和集。前5个最优特殊和集如下所示。
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}
似乎对于一个给定的最优特殊和集A = {a1, a2, … , an}，下一个最优特殊和集将是B = {b, a1+b, a2+b, … ,an+b}的形式，其中b是集合A“正中间”的元素。
应用这条“规则”，我们猜测对于n = 6的最优特殊和集将是A = {11, 17, 20, 22, 23, 24}，相应的S(A) = 117。然而，事实并非如此，我们的方法仅仅只能找出近似最优特殊和集。对于n = 6，最优特殊和集是A = {11, 18, 19, 20, 22, 25}，相应的S(A) = 115，对应的集合数字串是：111819202225。
若集合A是n = 7时的最优特殊和集，求其对应的集合数字串。
解题
题目坑了我好久
注意几点：
1.上面说的A的子集 B 和C ，B C 只是其中的任意两个子集，不是 B 和C的并等于A
2.A的任意子集都要满足上面两个条件，同时注意：B和C不能有交集
3.题目要求的是对于n的最优特殊和集，通过上面调整的是最近特殊和集，最优特殊和集在同样的n的情况下，其集合的和是最小的
4.7个数不相同，还是升序的
暴力解题：
1.在{19,30,37,38,39,41,44} 7个点附近寻找
2.求出所有的子集
3.对不相交的子集，利用题目给的两个条件进行求解
4.和最小的集合就是答案
下面程序参考了Mathblog，但是其是先求出每个子集的和，对于子集交集的没有看到，我改成求出所有的子集，再暴力找满足条件的值。
下面程序中在组合成初始集合A，最不好的方法也不是严格的在{19,30,37,38,39,41,44} 附近寻找的。同时，是用ArrayList当作集合用表示不是很好
JAVA
package Level4; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.FileReader; import java.io.IOException; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.TreeSet; public class PE0103{ // 对{20, 31, 38, 39, 40, 42, 45} //255 中的每个点+-3暴力求出所有的可能 // {19,30,37,38,39,41,44} //248 public static void run(){ int a[] = {19,30,37,38,39,41,44}; int min = -3; int max = 3; int c1[] = {19 ,30, 37, 38, 39, 41,44}; int c2[] = {19 ,31, 38, 39, 40, 42, 45}; int c3[] = {20, 31, 38, 39, 40, 42, 45}; int c4[] = {6, 9, 11, 12, 13}; int c5[] = {11, 18, 19, 20, 22, 25}; System.out.println(isOptimum(c1)); System.out.println(isOptimum(c2)); System.out.println(isOptimum(c3)); System.out.println(isOptimum(c4)); System.out.println(isOptimum(c5)); for(int a0 = a[0] ;a0<=a[0]+ max ;a0++){ for(int a1 = a0+1;a1<= a[1]+max ;a1++){ for(int a2 = a1+1;a2<=a[2]+max ;a2++){ for(int a3 = a2+1;a3<=a[3]+max ;a3++){ for(int a4 = a3+1;a4<=a[4]+max ;a4++){ for(int a5 = a4+1;a5<=a[5]+max ;a5++){ for(int a6 = a5+1;a6<=a[6]+max ;a6++){ int[] b= {a0,a1,a2,a3,a4,a5,a6}; if(isOptimum(b)){ String str = printArrStr(b); str = str + " SUM:"+sum(b); System.out.println(str); } } } } } } } } } public static String printArrStr(int[] a){ String str =""; for(int i=0;i<a.length;i++){ str +=" "+a[i]; } return str; } public static String printArrStr(ArrayList<Integer> list){ String str =""; for(int i=0;i<list.size();i++){ str += " "+list.get(i); } return str; } // 验证 是否是最优子集 // 子集 一个集合可能有多个子集，而下面的程序只是看成两个自己的情况，两个子集的并集等于原来集合，照成程序有问题 public static boolean isOptimum(int[] a){ // 所有的子集 ArrayList<ArrayList<Integer>> sets = MakeSubsets(a); int size = sets.size(); // System.out.println(size); for(int i=0;i<size;i++){ ArrayList<Integer> set1 = sets.get(i); for(int j=i+1;j<size;j++){ ArrayList<Integer> set2 = sets.get(j); if(!isDisjoint(set1,set2)){ int sum1 = sum(set1); int sum2 = sum(set2); if(sum1 == sum2) return false; if(set1.size() > set2.size() && sum1 <=sum2) return false; if(set1.size() < set2.size() && sum1 >= sum2) return false; } } } return true; } // 求集合内元素的和 public static int sum(ArrayList<Integer> set){ int sum = 0; for(int i=0;i< set.size();i++){ sum += set.get(i); } return sum; } public static int sum(int [] a){ int sum = 0; for(int i=0;i< a.length;i++){ sum += a[i]; } return sum; } // 两个子集元素是否相交 true 相交 false 不相交 public static boolean isDisjoint(ArrayList<Integer> set1,ArrayList<Integer> set2){ int size1 = set1.size(); int size2 = set2.size(); ArrayList<Integer> set = new ArrayList<Integer>(); for(int i=0;i<size1;i++){ int element = set1.get(i); if(set.contains(element)) return true; else set.add(element); } for(int i=0;i<size2;i++){ int element = set2.get(i); if(set.contains(element)) return true; else set.add(element); } set.clear(); return false; } // 求出所有子集的和 public static int[] MakeSubsetSums(int[] a){ int b[] = new int[(int)Math.pow(2, a.length) ]; for(int i=1;i<b.length;i++){ b[i] = MakeSubsetSum(a,i); } return b; } // 求出所有的子集 public static ArrayList<ArrayList<Integer>> MakeSubsets(int a[]){ ArrayList<ArrayList<Integer>> sets = new ArrayList<ArrayList<Integer>>(); for(int i=1;i<= (int) Math.pow(2,a.length);i++){ ArrayList<Integer> set = MakeSubset(a,i); sets.add(set); String s = printArrStr(set); // System.out.println(s); } return sets; } // 求出子集 public static ArrayList<Integer> MakeSubset(int[] a,int m){ ArrayList<Integer> set = new ArrayList<Integer>(); for(int i=0;i<a.length ;i++){ if( m>0 &&(m&1)==1){ set.add(a[i]); } m =m>>1; } return set; } // 求子集的和 // 利用 和 1 进行与运算 并移位 // 001001 相当于根据 1 所在的位置取 第 2 第 5的位置对应的数 // &000001 //---------- // 1 取出该位置对应的数 // 下面右移一位后 // 000100 // 下面同理了 public static int MakeSubsetSum(int[] a,int m){ int sum = 0; for(int i=0;i< a.length;i++){ if( m>0 && (m&1) == 1) sum +=a[i]; m >>=1; } return sum; } public static void main(String[] args){ long t0 = System.currentTimeMillis(); run(); long t1 = System.currentTimeMillis(); long t = t1 - t0; System.out.println("running time="+t/1000+"s"+t%1000+"ms"); } }
结果
20 31 38 39 40 42 45 SUM:255
20 32 39 40 41 43 46 SUM:261
20 33 40 41 42 44 47 SUM:267
21 32 39 40 41 43 46 SUM:262
21 33 40 41 42 44 47 SUM:268
22 33 40 41 42 44 47 SUM:269
running time=164s431ms
第一个就是答案，可以看出，直接根据第6个最优特征子集也可以推出下一个最优特殊子集
Python 质量也是好差
# coding=gbk import time as time import re import math import numpy as np def run(): a= [19,30,37,38,39,41,44] f = lambda x:x+1 a0 = map(f,range(16,22)) a1 = map(f,range(27,34)) a2 = map(f,range(34,41)) a3 = map(f,range(35,42)) a4 = map(f,range(36,43)) a5 = map(f,range(37,44)) a6 = map(f,range(41,48)) for a in a0: for b in a1: for c in a2: for d in a3: for e in a4: for f in a5: for g in a6: if a<b and b<c and c<d and d<e and e<f and f<g: A = [a,b,c,d,e,f,g] if isOptimum(A): print A,' ',sum(A) # [20, 31, 38, 39, 40, 42, 45] 255 # [20, 32, 39, 40, 41, 43, 46] 261 # [20, 33, 40, 41, 42, 44, 47] 267 # [20, 34, 37, 39, 40, 41, 48] 259 # [21, 32, 39, 40, 41, 43, 46] 262 # [21, 33, 40, 41, 42, 44, 47] 268 # [22, 33, 40, 41, 42, 44, 47] 269 # running time= 52.3980000019 s def isOptimum(a): sets = subSets(a) # print len(sets) for i in range(len(sets)): for j in range(i+1,len(sets)): s1 = sets[i] s2 = sets[j] if isDisjoint(s1,s2) == False: sum1 = sum(s1) sum2 = sum(s2) len1 = len(s1) len2 = len(s2) # print s1,' ',s2 if sum1 == sum2:return False if len1>len2 and sum1<=sum2:return False if len1<len2 and sum1>=sum2:return False return True def isDisjoint(b,c): for bi in b: if bi in c: return True return False def subSets(a): l = 2**len(a) sets = [] for i in range(1,l): s = subSet(a,i) sets.append(s) return sets # 求一个子集 def subSet(a,m): s = [] for i in range(len(a)): if (m&1)==1: s.append(a[i]) m =m>>1 return s t0 = time.time() run() t1 = time.time() print "running time=",(t1-t0),"s"