用VBA解欧拉计划题目（103）--特殊的子集和：最优解

grf1973

特殊的子集和：最优解

记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时的最优特殊和集，求其对应的集合数字串。

grf1973

103，105，106三题都是一个类型的，非常难理解。
103题是参考网上做法，给定一个近似的最优解，然后对每个元素+-3遍历，找出符合条件的最优解。
关键是不知道初始的近似解是怎么得出来的。

grf1973

。。。。。。。。。

grf1973

感觉应该有更好的办法做集合检验。我的是笨办法。

grf1973

103题初始集合Array(19, 30, 37, 38, 39, 41, 44)不知怎么来的。

香川群子

grf1973 发表于 2017-12-30 19:55
103题初始集合Array(19, 30, 37, 38, 39, 41, 44)不知怎么来的。

已知n=6的正确集合A={11, 18, 19, 20, 22, 25}



按预测规则，取中间数字19作为首位，其余的依次加19即可得到:{19,11+19, 18+19, 19+19, 20+19, 22+19, 25+19}
就是{19，30, 37, 38, 39, 41, 44}了。

grf1973

嗯，有道理。那这道题也算真正解出来了。

香川群子

n=7时，根据n=6猜测得到的{19,30,37,38,39,41,44}并不是满足条件的集合解。

因此，采取-1/1范围调整，很快就得到满足条件的一个集合解：S(A)=255 {20,31,38,39,40,42,45}
耗时 0.699s

如果调整计算范围扩大至-3/3，不知道是否有更优解。但是耗时会大增。

香川群子

花了266秒走完了，没有找到更优解。

然后优化剪枝了一下，只用22秒就能算完，列出所有满足条件解如下：
255 20313839404245
261 20323940414346
267 20334041424447
262 21323940414346
268 21334041424447
269 22334041424447
22.363s

香川群子

回过头重新计算一下n=6 （以n=5的猜测Array(0, 11, 17, 20, 22, 23, 24) 'S(A)=117为基础）

计算1秒出结果：
119 111721222325
115 111819202225
122 111821232425
124 111822232426
123 111921222327
127 111922242526
129 111923242527
125 112021222427
132 112023252627
123 121821222426
123 121821232425
125 121822232426
127 121822242526
129 121823242527
121 121920212326
128 121922242526
130 121923242527
132 121923252627
133 122023252627
129 131922232527
129 131922242526
131 131923242527
133 131923252627
127 132021222427
134 132023252627
135 142023252627
1.063s 115 111819202225