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

質問

【問題】
無作為に選ばれた＜m人＞の人間がいます。
その人間をランダムに並べて列を作ります。
その列を先頭から順番に＜nグループ＞に分けたとします。
◎イメージ
　1,2,3,4|5,6|7,8,9,10|11,12・・・m

この時、各グループの1列目（先頭）で最年長の人の年齢＋2列目で最年長の人の年齢＋・・・＋グループ最後列の最年長の人の年齢の合計が、最も少なくなるグループの切り方を求めたい。

なお、各人の年齢は列に対応して＜p[t]＞とする。（※t=0～m-1）

【条件】
4人のグループや2人のグループが出来ますが、いない列については無視してください。
上記のケースでは、2人のグループは３列目がいないので計算に含めない（＝0歳扱い）とします。

グループの人間の数が取りうる範囲は「1～m-残りのグループ数」です。
（残りのグループも最小値が1人なので）

グループに配置する人間は先頭から順に選ぶところにご注意ください。
１グループに、1人目,3人目、2グループに2人目ってことは出来ません。

----------------------------------------------------------------------

いまいち良いアルゴリズムが思い浮かばないのですが、
皆様ならどのように解きますか？

回答No.2

ORUKA1951 · ベストアンサー

出来たグループの計算は難しくないと思いますので、グループ分けの方法について考えて見ます。
m,nについて、各グループに必ず1名はいますから、m-n+1がグループの最大人数(M)になります。
5人を3に分けるなら、5-3+1=3
８人を4つに分けるなら、8-4+1=5　5,1,1,1

そこで、要素数(m-n+1)個の空の配列を用意します。
例) 5人を3つ---(0,0,0)、8人を(0,0,0,0,0)
　汎用的には
　L0～Ln
　L0{L00,L01,L02・・・・L0(m-n)}
　L1{L10,L11,L12・・・・L1(m-n)}
　・・・・・・・・・・
　L(n-1){L(n-1)0,L(n-1)2,L(n-1)3・・・・L0(m-n)}

ついで、次の手順で循環します。
MをL0～L(n-1)に入れていく
5,3の場合、3,1,1　　1,3,1　　1,1,3
8,4の場合、5,1,1,1　　1,5,1,1　　1,1,5,1　　1,1,1,5

Mから引く数の最大数をaとする。a<M/2
それを次のように置く
M-a,1+a,1,1,1,・・・,1
M-a,1,1+a,1,1,・・・,1
M-a,1,1,1+a,1,・・・,1
・・・・・
M-a,1,1,1,1,・・・,1+a

ここで、a>2のとき同様にb<a/2の範囲でかつb>=1
M-a,1+a-b,1+b,1,1,・・・,1
M-a,1+a-b,1,1+b,1,・・・,1
M-a,1+a-b,1,1,1+b,・・・,1
・・・・
M-a,1+a-b,1,1,1,・・・,1+b
を行う、
・・次に、M-aの位置をずした場合も同様に
1+a,M-a,1,1,1,・・・,1
について行う。

これを値のとりうる範囲内続ければよいかと

ちなみに、
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):3,1,1
(2):1,3,1
(3):1,1,3
(4):2,2,1
(5):2,1,2
(6):1,2,2
ですね。
８人を4グループに分けるときは
(1) 5,1,1,1
(2) 1,5,1,1
(3) 1,1,5,1
(4) 1,1,1,5

(5) 4,2,1,1
(6) 4,1,2,1
(7) 4,1,1,2
(8) 2,4,1,1
(9) 1,4,2,1
(10)1,4,1,2
(11)2,1,4,1
(11)1,2,4,1
(12)1,1,4,2
(13)2,1,1,4
(14)1,2,1,4
(15)1,1,2,4

(16)3,3,1,1
(17)3,1,3,1
(18)3,1,1,3

(19)3,2,2,1
(20)3,2,1,2
(21)3,1,2,2
(22)2,3,2,1
(23)2,3,1,2
(24)1,3,2,2
(25)2,2,3,1
(26)2,1,3,2
(27)1,2,3,2
(28)2,2,1,3
(29)2,1,2,3
(30)1,2,2,3

かな・・・

お礼

ご回答が遅くなり申し訳ありません。
机上シミュレーションをしたのですが、いまいち分かりませんでした・・・。

ただ、ご回答頂いた内容をヒントに、再帰関数で解決しました。

ループ：ｘ←１；ｘ＜＝ｍ－ｎ＋１；ｘ＋＋
ｎ＝１の場合）
１．残りの数を自分の値として関数を抜ける。
ｎ＞１の場合）
１．ｘを自分の値とする。
２．ｍ←ｍ－ｘ、ｎ←ｎ－１で自分を呼び出す。

ご教示いただきありがとうございました。

補足

ご回答ありがとうございます。返事が遅くなり申し訳ありません。
平日はなかなかシミュレーションする時間が取れず、せっかくご回答頂いたのに確認が取れていません。
土日でじっくり検討してみます。

回答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]から解を求める手続きです。

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