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