# 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](p105)と[問題106](p106)に関連している.
