Problem 103 の編集

*[[Problem 103:http://projecteuler.net/problem=103]] 「特殊和集合:最適化」 [#mda67ebe]
大きさ &tex{n}; の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう.
>
i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.~
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.

ある &tex{n}; に対し S(A) が最小化されていれば, それを最適特殊和集合と呼ぼう. はじめの 5 つの最適特殊和集合は下に与えられる.
>
&tex{n}; = 1: {1}~
&tex{n}; = 2: {1, 2}~
&tex{n}; = 3: {2, 3, 4}~
&tex{n}; = 4: {3, 5, 6, 7}~
&tex{n}; = 5: {6, 9, 11, 12, 13}

ある最適特殊和集合 A = {&tex{a_{1}};, &tex{a_{2}};, ... , &tex{a_{n}};} に対し, 次の最適特殊和集合は B = {&tex{b};, &tex{a_{1}+b};, &tex{a_{2}+b};, ... ,&tex{a_{n}+b};} となりそうである. ここで &tex{b}; は前列の「中央の」要素である.

この「法則」を用いると &tex{n}; = 6 に対する最適特殊和集合は A = {11, 17, 20, 22, 23, 24} で, S(A) = 117 と予期するだろう. しかしこれは, 最適に近い集合を与えるアルゴリズムを用いたにすぎないため, 最適特殊和集合とはならない. &tex{n}; = 6 に対する最適特殊和集合は A = {11, 18, 19, 20, 22, 25} で, S(A) = 115 である. これに対応する集合の文字列は 111819202225 である.

A を &tex{n}; = 7 に対する最適特殊和集合とするとき, その集合の文字列を求めよ.

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

タイムスタンプを変更しない

A を &tex{n}; = 7 に対する最適特殊和集合とするとき, その集合の文字列を求めよ.

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

テキスト整形のルールを表示する