数値を複数の群に分ける最適な組み合わせを求める方法

質問

次のような問題をCで記述するにはどのようにすればいいでしょうか？

要素数が不定の整数値配列がある。
この配列の各要素を、与えられた個数の群に分ける。
条件として、与えられた数値列で隣り合う数値しか同じ群に含めることは出来ない。

例：
数値列は{5,2,7,12,6,15,4}
群の個数を3とする。

(1) {5,2},{7,12,6},{15,4}
(2) {5},{2,7},{12,6,15,4}
(3) {5,2,7},{12},{6,15,4}
・・・

と複数の組み合わせがある。
これらの組み合わせのうち、各群の合計値が最も均等になるような組み合わせを求める。最大値と最小値の差が最小となる組み合わせを最も均等と考える。

上の例であれば、各群の合計値と、合計値の最大値と最小値の差は、

(1) {5,2},{7,12,6},{15,4} ==> 7,25,19 (25-7=18)
(2) {5},{2,7},{12,6,15,4} ==> 5,9,37 (37-5=32)
(3) {5,2,7},{12},{6,15,4} ==> 14,12,25 (25-12=13) ☆

のようになり、この３つの中で最も均等なのは

(3) {5,2,7}{12}{6,15,4}

となる。
実際は、これ以外の組み合わせでより均等となるものがあるかと思います。

この問題そのものが必要なわけではなく、この結果を利用して別のある問題を解決しようとしています。

数値の数が増えると組み合わせの数も大幅に増えて計算時間に影響すると思います。
全ての組み合わせを試すことなく答えにたどり着く方法があれば、考え方だけでも提示頂ければと思います。

回答No.27

amanojaku1 · ベストアンサー

>回答No.23　amanojaku1

「2018/06/15 03:48:47」の時点で修正しました。
それ以前にコピーしている場合は注意して下さい。

数値を複数の群に分ける最適な組み合わせを求める方法
http://ashtarte.pa.land.to/utf8/smt.cgi?r+sara/&bid+000000DC&tsn+000000DC&bts+2018/06/15%2002%3A04%3A46&

お礼

コメント追加して頂きありがとうございます。今頑張って理解しているところですが、何となく分かってきました。

それにしても２進数の数学的特徴をうまくこの問題に当てはめるという発想が凄いですね。問題の本質は順列のパターンを網羅することですが、私は再帰を使うイメージしかなかったです。

回答No.1

bunjii

>考え方だけでも提示頂ければと思います。
貼付画像は手作業で作成したものです。
同等の組み合わせ配列を配列変数に作成すれば判断できるはずです。
元の配列は大きくなれば作業に必要な配列が増えますので効率の良いアルゴリズムを考えてみると良いでしょう。
プログラムを組むときにフローチャートを書くと処理の誤りを防げると思います。

お礼

ご回答ありがとうございます。
お聞きしたかったのは、その組み合わせを網羅するコードはCでどのように書けば良いかということでした。
さらに突っ込んで、全組み合わせを網羅せずに済む方法や、「均等」という概念をより数学的な条件に置き換えて効率的なアルゴリズムが組めないか考えて頂けると助かります。