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ベストアンサー
- 回答日時:
それは宿題ですか?
NP問題?
ナップサック問題?
たぶん、これを簡単に解けるようなアルゴリズムを作れたら、世界的に有名になれるほどの問題です。(一部のマニアックな人たちの間だけですが・・・)
完全な正解ではなく、近似でよいのであれば、できるかもしれませんが。
総当たりで行う場合の効率よくやるやり方はわかりません。地道に総当たりするしかないと思います。(NP問題の反例は私には見つけられません。)
効率というのが数学的な効率ではなく、コンピュータ上の効率という意味であれば、いろいろとあると思いますが。メモリの配列の使い方とか。
No.2
- 回答日時:
あれ? 問題がおかしい.
比は r(1):r(2):...:r(n-1):r(n)
ですか? そうじゃないと s(i), i ≦ i ≦ n にあいませんよね.
で, 3つ以上のグループにわけるときに「一番近い」というのを定義する必要もあります.
とりあえず n=2 に対してはナップサック問題になりそう. もしそうなら NP-困難だけど DP 使えば FPTAS までいけるかな.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 統計学 確率統計の問題です。 3 2022/04/07 04:39
- Excel(エクセル) 指定した数字まで累計する方法や文字例の抽出について教えてください 4 2022/10/05 21:19
- 友達・仲間 12月23日〜25日で友達グループ①と旅行に行く予定なのですが、最近あまり好きじゃなくなってきて、 1 2022/11/14 23:02
- 数学 数学Aについて分からない問題があります。 答えは載っているので分かりますが、 解き方がわかりません。 5 2023/02/03 18:58
- Excel(エクセル) SUMIF関数について 4 2023/06/14 13:13
- LINE LINEグループの一人と別のやり取りがしたい 5 2022/05/26 16:00
- 英語 効果的なグループ学習について 2 2023/02/22 22:10
- Java Java 南京錠 2 2023/02/04 11:46
- その他(恋愛相談) 僕の考えている事はアプローチになりますかね?同じ大学のサークルの同級生の女子が好きです。その子にアプ 1 2022/09/09 22:50
- 子育て ママ友グループLINE抜けたい 9 2022/05/30 10:09
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
Stuck
-
アルゴリズムとプロトコールの違い
-
画像から文字を認識してテキス...
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
期間重複チェックがわかりません
-
gooという検索エンジンの後にGo...
-
2つのテキストファイルを比較...
-
ハッシュアルゴリズム
-
理系の高校生です。大学で情報...
-
あいまい検索(文字列一致率)
-
デジタル時計のアルゴリズム
-
経路探索について
-
グループを均等に分けるには?...
-
m個の数字をn個のグループに分...
-
乱数って・・・
-
確率論的な麻雀の勝ち方を教え...
-
多変数関数の最小値を求めるプ...
-
OpenCVのライセンスについて
おすすめ情報