103 : 特殊和集合:最適化

大きさ$n$の集合$A$の要素の和を$S(A)$で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合$B$と$C$に対しても以下の性質が真であれば,$A$を特殊和集合と呼ぼう.

1. $S(B) ≠ S(C)$; つまり, 部分集合の和が等しくてはならない.

2. $B$が$C$より多くの要素を含んでいればこのとき$S(B) > S(C)$となる.

ある$n$に対し$S(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 = \{a_1, a_2, \dots , a_n\}$に対し, 次の最適特殊和集合は$B = \{b, a_1+b, a_2+b, \dots ,a_n+b\}$となりそうである. ここで$b$は前列の「中央の」要素である.

この「法則」を用いると$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$に対する最適特殊和集合とするとき, その集合の文字列を求めよ.

注意: この問題は問題105と問題106に関連している.