グループ毎の年齢を計算するアルゴリズムについて

質問

• グループ毎の年齢を計算するアルゴリズムについて説明します。
• 無作為に選ばれた人間をランダムに並べて列を作り、その列を複数のグループに分ける際に、各グループの最年長の人の年齢の合計が最も少なくなるグループの切り方を求める問題です。
• 具体的な条件や注意点も説明します。

回答No.1

ORUKA1951

いまいち条件がわかりません。
＞なお、各人の年齢は列に対応して＜p[t]＞とする。（※t=0～m-1）
の意味がわかりません。最初の配列の数ではなく、出来上がった【列】ですか？そうすると重複します。
　それぞれの年齢をage{'0'}～age{'m-1'}じゃないのですか？

＞4人のグループや2人のグループが出来ますが、いない列については無視してください。
　以内列はないのでは？nグループに分けると言う処理の時点ですべてのグループにいます。

＞上記のケースでは、2人のグループは３列目がいないので計算に含めない（＝0歳扱い）とします。
　三人目、二人目はいなくても、「最年長の人」は必ず存在します。もし、そういう条件なら、はじめから三人以上のグループに分けるとか、任意の人物を外すとかすればよい。

補足

ご回答ありがとうございます。補足します。

>最初の配列の数ではなく、出来上がった【列】ですか？そうすると重複します。
>それぞれの年齢をage{'0'}～age{'m-1'}じゃないのですか？

最初の配列です。

例えば、m=5,n=3のケースを考えます。
素データ：18歳、22歳、25歳、25歳、60歳

ランダムに並べますので、以下のとおりになったとします。
25,18,60,25,22
つまり、p[t]の値は以下のとおりとなります。
p[0]:25
p[1]:18
p[2]:60
p[3]:25
p[4]:22

ここまでは問題で与えられると考えてください。
（もちろん、実際の数値ではなく、m,n,p[t]というかたちですが）

n=3ですので、5人を3グループに分けます。
グループ分けは以下のケースが考えられます。
(1):1,1,3
(2):1,2,2
(3):1,3,1
(4):2,2,1
(5):3,1,1

(1)のケースを考えます。(1,1,3)
グループ1：25(1列目)
グループ2：18(1列目)
グループ3：60(1列目),25(2列目),22(3列目)
この場合、1列目はグループ1：25、グループ2：18、グループ3：60なので、最大値は60、
2列目はグループ1,2に対象者がいないので、グループ3の25
3列目もグループ1,2に対象者がいないので、グループ3の22
よって、(1)のケースは60+25+22=107となります。

同じく、(2)のケースを考えます。(1,2,2)
グループ1：25
グループ2：18,60
グループ3：25,22
この場合、1列目の最大年齢は25、2列目の最大年齢は60、
よって、(2)のケースは60+25=85となります。

この作業を全てのケースで行うと以下のようになります。
(3)のケース：25+60+25=110
(4)のケース：60+25=85
(5)のケース：25+18+60=103

最小ケースを求めるので、最小値は85のケースです。
よって、答えは(2)、(4)のケースとなります。

計算の流れは以上です。

実際に求めるアルゴリズムはm,n,p[t]から解を求める手続きです。

他にご不明な点があればご指摘ください。