m個の数字をn個のグループに分けるとき、

質問

m個の数字をn個のグループに分けるとき、
各グループの和s(i) ,(1<=i<=n) が、指定した比
r(0):r(1): ・・・ :r(n-1):r(n) ( = s(0):s(1): ・・・ :s(n-1):s(n) )
に一番近くなるようなグループ分けを導けるアルゴリズムはありますか。

例えば、{1, 3, 4, 6}を和の比が1:2に一番近くなるように2つのグループに分けると、
{1, 4}, {3, 6}
となります。(もし違ってたら指摘してください)

アルゴリズムでなくても、こうしたら良いんじゃないか、という考えがありましたら
教えてください。
総当たりで調べる場合はどのようにすれば、効率良く調べられるかという点もお願いします。

よろしくお願いします。

回答No.1

wildcat-yp · ベストアンサー

それは宿題ですか？
NP問題？
ナップサック問題？
たぶん、これを簡単に解けるようなアルゴリズムを作れたら、世界的に有名になれるほどの問題です。（一部のマニアックな人たちの間だけですが・・・）

完全な正解ではなく、近似でよいのであれば、できるかもしれませんが。

総当たりで行う場合の効率よくやるやり方はわかりません。地道に総当たりするしかないと思います。（NP問題の反例は私には見つけられません。）

効率というのが数学的な効率ではなく、コンピュータ上の効率という意味であれば、いろいろとあると思いますが。メモリの配列の使い方とか。

回答No.2

Tacosan

あれ? 問題がおかしい.
比は r(1):r(2):...:r(n-1):r(n)
ですか? そうじゃないと s(i), i ≦ i ≦ n にあいませんよね.
で, 3つ以上のグループにわけるときに「一番近い」というのを定義する必要もあります.
とりあえず n=2 に対してはナップサック問題になりそう. もしそうなら NP-困難だけど DP 使えば FPTAS までいけるかな.