動的計画法を用いるアルゴリズムの開発

以下の問題を考えています。私には手におえないので、
教えて頂けないでしょうか？
日頃からアルゴリズムについて御詳しい、プログラマの方々
なら、お分かりになるかなあ？と思います。

問題
n個の整数の列i_1,i_2,.....,i_nがある。この整数列をk個の「仕切り」
によって、k+1のグループに分割し、グループに含まれる整数の和を最小
にしたい。
動的計画法により最適な分割を求めるアルゴリズムゐ開発せよ。

例
15,3,7,6,10,4
という整数が与えられた場合は、
15|3,7,6|10,4
が最適な分割で、和が最大のグループは２番目で
16である。

解決しました

----------------- 糸冬 -----------------

俺も初心者なんで、答えが知りたいです。
動的計画法ってなんですか？

そうだそうだ、1は結果をちゃんと書いてくれ

俺も結果が気になってきた・・・

その分割は何の為にするの？
圧縮関連の話？

>>3
臨機応変な家族計画

俺なら､

K個の箱に､箱の中の総和が一番小さい箱に､一番大きい数を入れるな

15,10,7,6,4,3
10,7,6,4,3-15||
7,6,4,3-15|10|
6,4,3-15|10|7
4,3-15|10|7,6
3-15|10,4|7,6
15|10,4|7,6,3

て事になるんだが､このアルゴリズムが動的計画法かどうかは知らんし
つか、問題が単純すぎるんじゃないの？こんなの最適解は小学生でも
判るだろ。もーっと難しい問題に適用すべき計画法じゃないのか？

とりあえず動的計画法について教えろや

動的計画法は、場合によってはかなり有用なアルゴリズムです。

問題を解くとき、全体を小さい単位の問題に分割して、それぞれを
解決することによって全体としての解を得る、という方法が一般的です。

８クィーンを例に挙げると、「チェス盤に８つクィーンを置く」という
目的を達成するために、１つのクィーンが置けるかどうかを８回判断して、
最終的な解を得る、という方法を（無意識に）考えますよね。
＃例が悪いかもしれない

それに対し、動的計画法とは、あらかじめその小さい問題を全て解いておいて、
必要に応じて解いた答えを索引し、最終的な答えを得る考え方です。

具体的な例、必要ですかね？そこまで行くと、なんかスレ違いの気分もします。

そういうアプローチなら､

15,10,7,6,4,3の総和は45なので、三つに分割すると､15になる
ただしこれは最適な解がそうなわけで、要素によってはそうならない
可能性がある。で、各箱が15に近付くように（超えない範囲で）数を入れる。

15,10,7,6,4,3-
10,7,6,4,3-15
7,6,4,3-15|10
7,6,3-15|10,4
6,3-15|10,4|7
6-15|10,4|7,3
この時点で､最後の数なので､一番総和の小さい箱に入れる
15|10,4|7,3,6

この考えも動的計画法かはわからんが、思考自体は､
「想定される最適解に近付くように、解を組み立てていく」
というもの。

やっぱり問題が簡単すぎるな。１は動的計画法のアルゴリズム自体を
知りたいのか､設問を解きたいのか､どっちなのだ？

数字の順番変えちゃいけないんじゃないの？

>>11
なんで？つか、数字の順番変える事に意味は無いだろ。
単に整頓されてるかされてないかの違いなだけで。

こういうのは、問題の本質を抽出する（ソートが本質かそうでないかを
判断する）事が肝要だから､11はこういう話には向いてないんじゃない？

>1
Nをそれぞれの数に対して積分してから変数変換してフーリエ変換してから偏微分。

>>13
もはやあわれ。

数列と集合を勘違いしてない？>>12
数列の要素には順番があるんだよ？

1です。ちょっと返信送れました。
すみません。
まず、数字の順番を入れ換えてはいけません。
説明ぶそくで済みませんでした。

この問題のヒントみたいなのが載っていたのですが、
(これってヒントになるのか？ってレベルですが)
ヒント
例によって、木状に探索していく。整数列に仕切りをいれて２つに
分割することで木を一段深くする。その時、元の列がi個の分割
なら一段下がったところは、i_1個とi_2個の分割(ただしi_1＋i_2＝i)
になっている)
というヒントがついていました。

僕が考えるに動的計画法は、
１、同じことの繰り返しによる、無だを省く
２、ボトムアップ
ということが指針だということなので、

まず、
1,2,3,4,5(数字はアイテム番号とする)
というアイテムを分割することを考える。
ここで、
(1,2)(3,4,5)と(1),(2,3,4,5)
という分割を考え、
さらにこれから先の分割を考えるとき、
一つ目の分割で、
1+2 < 3+4+5
とすると、
明かに(3,4,5)を次は分割しようとするはずである。

ここで、２つ目の分割
(1)(2,3,4,5)
をさらに分割しようとすると、
すでに最初の分割(1,2)(3,4,5)
で
1+2 < 3+4+5
ということが分かっているから、
(1)(2)(3,4,5)
という分割パターンは最初から、考えなくていいということになり、
計算時間が短縮できる。
ということだと思います。

これをアルゴリズムとして、気持のいい形にかきたいんだけど、
どうやったらいいのかな？って思って悩んでいます。

(もっといい考え方＋拡張があれば教えてください！)

ざまみろ 12>>
お前の方が向いてないんだよ。

勿論２は僕じゃないです。
あと、有益なヒントとして、以下の情報を持っています。

動的計画法を適用できる多くの問題にもれず,
この問題も部分問題によって(定式化にしたがった)木を構成できます.
そこでこの木の根に相当する問題の解を求めるというのが
我々の目的なんですが,
動的計画法ではこの木の一番下の子の部分から
ボトムアップ式に解を覚えつつやっていこうというのが
方針だと思われます.

ちなみに O(kn^2) でできました.
(たぶんこれが正解でしょう)

問題がよくわからん。
「グループに含まれる数の和を最小」ってどういうこと？
文面通り受け止めると、
1,2,3,4,5,6,7,8→1|2|3|4|5|6|7|8
グループに含まれる最小の数：１、最大の数：８

問題はかなり抽象的というか、数学ぽい考えというか
難解な感じで、説明しにくいです。
でも、これが、与えられた問題で、一字たりとも変えていません。

まず、
k個の「仕切り」のkは定数です。
また、nも定数です。

プログラマの皆さんは、アルゴリズムに熟知してらっしゃると
思うのですが。

この問題の意味がわからないというのは、かなりヤバいと思うが。。

最初にあった例では、
仕切りが２つ、グループは３つですよね。

この整数の数を増やしていくと、
それを例えば４つの仕切りで分割しろといわれても、
最適なものを調べるには、
全部総あたりで、計算すると大変なことになりますよね。

これを動的計画法で解決したいのです。

動的計画法の詳しい説明はかんべんしてください。

つーか課題？

しきりの数は任意？

>>24
そうです。〆切明後日です。
結構考えてるんですが、できない。

>>25
仕切りの数は定数kです。

これを機会に動的計画法について勉強してみたらおもしろいと思います。

kが変数だと思ってた……鬱氏

結構動的計画法ってはまるとおもろいですね。
感想だけなのでさげ

あげ

１）グループの和が総和/ｋなら部分的に最適とは言える。
２）全てのグループの和が総和/ｋなら最適。
３）全てのグループの和と総和/ｋの差が（総和/ｋの余り）/k＋１
以内であるなら最適。

つうことで後よろしく。

動的計画法のからみは？

>>1
動的計画法にうってつけの問題ですね
簡単に出来ますよ。ただ説明を書くのは辛いです。
ソースなら提示できそうですが……

>>30さんの方法は、これだけの文面ではよくわからないのですが、
もうちょっと詳しく教えてもらえませんか？

PTASとかFPTASとか超懐かしいねえ。10と30はヴァカだけど。

寝る前に頑張って説明してみよう。

例えば、15,3,7,6,10,4,13,2,3,6　という１０個の数に、
区切りを３つ入れる場合について考えてみます。
この場合、下の図のようなテーブルをプログラムで作成すればいいわけです。
（等幅で見てね）

15 3 7 6 10 4 13 2 3 6
区切り残り０：10,69 9,54 8,51 7,44 6,38 5,28 4,24 3,11 2, 9 1, 6
区切り残り１： 4,38 4,28 4,27 3,24 2,24 2,17 1,13 2, 6 1, 6 1, 6
区切り残り２： 3,25 2,24 3,23 2,17 2,14 1,13 1,13 1, 6 1, 6 1, 6
区切り残り３： 2,23 3,16 2,14 1,14 1,13 1,13 1,13 1, 6 1, 6 1, 6

例えば左下の(2,23)が何を表しているかというと、
「区切りがまだ３つ使える場合、
　　次の最適な区切りはここから２つ目の場所、
　　その場合の最大値は23になりますよ」
という事です。すなわち、１つ目のグループは[15,3]が正解だと解るわけです

これがわかれば、問題は、
「7,6,10,4,13,2,3,6　という８個の数に区切りを２つ入れる」
という風に変わります。
その場合は(3,23)、すなわち２つ目のグループは[7,6,10]とわかります。

このように追っていくと、答えは[15,3]、[7,6,10]、[4,13]、[2,3,6]となります。
（続く）

さて、このような表をどうつくるかという問題ですが、
それは自分で考えてください。

ヒントは、
・区切り残り０の場合は単純計算です。
・区切り残りＮの場合が解っていれば、Ｎ＋１の場合もわかります。

例：（等幅）
区切り残り４： 1,16 1,14 2,13 1,13 1,13 1,13 1,13 1, 6 1, 6 1, 6

数学的帰納法により、全ての場合の表が求まります。

わかりにくいかもしれませんが、もし動的計画法の知識があれば、
割合すんなりと読めるのではないでしょうか？甘い？>>1さん

>>22
つうか、問題文に厳密さがかける、っていうのが真実だろ。

「n個の任意の自然数からなる数列 i_1, i_2, ..., i_nがある。この
整数列をk個の「仕切り」によってk+1のグループに分割し、グ
ループに含まれる整数の和を最小にしたい。kは0以上n-1以下の
定数で、任意に指定することができるとする。動的計画法により
最適な分割を求めるアルゴリズムを開発せよ。」

こんなかんじか？

>>34-35
なるほどね。動的計画法というものが理解できた。計算量はO(KN)程度かな。

>>34, >>35
なるほどなるほど。解き方はわかったつもりなのだが、テーブルの1列目以外
を求めているのはなぜ？

２列目以降がないと、１列目は出ないからじゃない？
同じく３列目以降がないと、２列目が出ないし。
だから、N列目から１列目に向かって解いて行くんだと思う。

俺も良くわからないけど、
確実にいえることは
０列目の情報は、計算しなくてもわかるので
入力とみることができて、
K列目までがわかれば、答えが出る
そういうわけで、39の言ってる事は正反対です

基本的には
一番右から順番に
数列の数が１個の場合、２個の場合・・・
を考えていくみたいだけど

補足しておけば、第４列を求める場合
右から13,2,3,6だけの場合考える余地が無い
この４つの数の列に
4を付け加えることを考えると
略
この５つの数の列に
１０を付け加えることを考える
この時の最適な区切り線を計算するには
区切り線を10の右につけた場合を考えると
第４列なので残り３本線を引くのだが、
10を取り除いた数列4,13,2,3,6
に３本線を引くときの最適な場所はすでに3列目で計算している
そして､その最大値と10を比較すれば・・・
このように、以前の計算を利用していくのだと思う

>>1
技術科学大学スレで７系の人にたずねるとよいぞ（ワ

>>40
列と行を勘違いしているっぽいけれど？
列は縦、行は横だよ

つーか厨房なので、ソース見せて下さい（涙）>>34

>計算量はO(KN)程度かな
違うと思う

確かに（ｗ
行と列逆に使ってる

今、起きて、犬の散歩から帰って来たところです。
みなさん、いろいろな御説明ありがとうございます。
今から学校に行かなければいけませんので、学校
のいきかえりと学校で、このスレを参考にひたすら考えます。

>>32=34 さん？
>ソースなら提示できそうですが……
どうかお願いします。動的計画法にはまってきたので、
いろいろ調べたいです。

教えて君じゃないことを証明するために、
４６の書いたコードを公開せよ

>>47
アルゴリズムを考えているので、コードは考えていないですよ。

age

>>36
自然数などという条件は付いてないと思うが。

>>1
あと１日考える価値のある課題だと思いますよ。
動的計画法の、しょうもないナップザック問題などに比べて、この課題はとても良くできています。
動的計画法にはまっているのであれば、この問題に是非挑戦してみてください。
（それに、安易に課題の解を求める人たちが増えても困りますから）

もし私の説明がわかりにくければ、とりあえずネットで「ナップザック問題」等で検索をかけ、
その説明と併せて読んで貰えるとわかるんじゃないかと思います。

頑張ってください。

>>38
39さんが言っているように、自分より右かつ上であるセルが全てわからないと
自分自身のセルが解けないためです。
右側から解いていっても、上側から解いていっても、本質的には同じです。
for文の順序が入れ替わるだけですね、きっと。

ナップサックもついこないだやったばっかなので、頑張ります。

やっと理解できました。次は、計算量の評価ですが、これが
いままで、やったことがないんです。

【前処理】
１）期待される最小のグループ和（総和/グループ数）を求める。
２）数列の頭からみていって「期待されるグループ和」を超えた所に壁を作っていく。
　　これが初期の遺伝子。

【メイン】
３）100本の配列を用意してこの遺伝子をコピーする。
４）乱数によって壁をひとつ選びこれを左または右に（乱数で決定）移動する。
５）最良の結果が出ればこれを別の配列に保存しておく。
６）この操作を100本の配列について100回行う。

７）100本の配列の中味を今までの最良の結果に置き換え、（３）〜（６）を繰り返す。

３）〜７）を数回繰り返せば最良の結果が出て来るだろう。

が？

これって遺伝的アルゴリズムと関係ありそうですね

７）見込みのない50本の配列の中味を今までの最良の結果に置き換え、（３）〜（６）を繰り返す。
　　−−−−−−−−

にした方が面白いかな。

Genetic Argorithm風アルゴリズム？
>４）乱数によって壁をひとつ選びこれを左または右に（乱数で決定）移動する。
このへんがGAじゃないね
最適化問題といえばGAだけど！？
でも、動的計画法の方が計算量が明らかに少ないね
この場合は・・・

よく知らないんですが「ナップザック問題」で検索して出てきた頁を読んで思いついたものです。

５８
そんなことするよか、全部のパターンを確かめた方が速いでしょ？
数が多すぎて全部のパターンを確かめられない上に、
適切なアルゴリズムが存在しない時に
初めて意味がある
最近は制御系にも応用され始めてる

「動的計画法」とやらを全く理解していないもんで。失礼しました。

結局、7が一番面白い

う〜ん、途中参加だが、俺も計算量が気になって来たぞ。
どんくらいに圧縮されるんだ？
ちなみに総当たりだと、指数的数字になるなあ。

関係ありそうだけどなさそうだった　死農

たいていのプログラマーってアルゴリズムに精通してないと思われ
だって､使う機会ほとんどないもん
一流大学でてるインテリ学生の一部でしょ
そういうのに詳しいのは
でもって、そういうのが一流プログラマなんだけどね

1です。計算量が求まりません。
噂では、 O(kn^2)だそうですが。なぜ？
締め切りまで１２時間きりました。

しかし、このアルゴリズム、はまったけど、まとめあげる
の大変やった。A４*3枚も説明に費した。
けど、他人が読んで分かるかなあ？
明日、また読み直して、書き直すかも？
お休みなさい。プログラマの皆さん。

Σ(1+2+・・・n)
=((n+1)n/2)k>=計算量

>>67
多分わかっていると思われるのですが、１さんへの説明チックに書きます。
計算量において、/2とか+1とかいう概念は存在しません。
あくまでもオーダーなので、定数プラスや定数倍などは評価されません。
だから、nlognの場合も、「logの底って何だろう？」という事はナンセンスになります（何でもいいんです）
最終的に67さんの式は、結局O(kn^2)となります（なぜその式が出るのかの考察はまだしていませんが）。

>>1
実際にコードを書いてみて、そのfor文に注目すると、計算量は（概算で）出ます。
理論で証明しようとするととたんに面倒になりますが、もしそれを授業でやっていないなら
実際にソースコードを示して、そこから計算量を示す方法が現実的でしょう。
ちなみに、私は（証明はしてませんが）O(kn^2)だと思っています。

>>65
例えば動的計画法なんて、まず普通しらないし、実際の場面で応用する機会もまずありません。
しかし、使用できる道具がいくつかあるというのは選択肢を広げる上で非常に重要だし、
実際に、まず実世界で使わないと思っていた「巡回セールスマン問題」なども、流通業界の仕事で
使用したという経験もあります（時間軸に従ったグラフを利用）

過去の人たちが様々な証明を行ってくれている方法なので、応用できる場面にて
数学的考証をしなくてすむので、知っていればいるほど応用範囲が広がるかと。
決して「一流大学を出ているインテリだけが知ってろ」などと思わずに、
機会があれば学んで貰えればと思います。

とはいえアルゴリズムオタクってのは、応用になれば途端に使えなくなるのが
常ですよね。まさに頭でっかち。
そういう意味では、一般社会で経験を積んだプログラマこそが一流なのかもしれません。

酔っているから支離滅裂で失礼。

課題の締切もすぎたことだし、
ソースをみせてくれないですか？>>68

レポート出しました。今回は本当にいろいろ
教えて頂きありがとうございました。
ソースは作成できませんでしたが(今日締め切り４本抱えていたため
余裕無しでした)動的アルゴリズムについては、かなり
いい感じに理解できたと思います。
なかなか面白い発想ですし、これから、リアルタイムに
使って行けたらいいなあ、と思います。

結局理解できてないわけ？
言い訳書いてるだけで、アンタからは技術的な発言無かったし

>>71
一年生なんだから仕方ないと思われ

もう終わっちゃったのかもしれないけど、私の予想。

最初はすべての整数が区切られているものとする。
整数がn個あるので区切りはn-1個あるとする。
もちろんこのときは分割は最適です。
さて、ここから区切りを一個取り除いても分割が最小になるには？
と考えて、ある区間内ににおける総和を求めて、その右にある区間における総和と足し合わせます。
その値が過去に調べたいずれの値よりも最小になるのが最適な「区切り」の取り除き場所です。
最小になるかどうかの調べかたは簡単ですよね。
で、一個取り除いたところでこれは区切りn個の時点で最適な分割になっています。
同じ手続きでさらに一個ずつ取り除いていき、k個の区切りになったところで終了。

間違ってるかも？

はー、よく考えてから書けっつーの
アルゴリズムは上の方にでてるから・・・・
それ読んでみれば、間違ってんのすぐ気づくよ

>74
お、間違ってると指摘されたよ。
かなり自信あったんだが。
他の人はどう思う？

>73
だいたい､その日本語じゃわからないって（笑）
人としゃべったことある君？

>>73
区切りのパターンが k→k+1 で複数変化する場合があるので、
(e.g.)
4 5 | 2 7 (k=1)
4 | 5 2 | 7 (k=2)

Greedyなアルゴリズムが常に最適解を与えるとは限らない。

>>73

６　３　１　３　６　９　　を３つに分けるとすると


６　３　１　３　６　９　　（スタート）
　＾　＾　＾　＾　＾

６　３　１　３　６　９　　（１個抜く）
　＾　＾　　　＾　＾

６　３　１　３　６　９　　（２個抜く）
　＾　　　　　＾　＾

６　３　１　３　６　９　　…　結果、最大13となるが
　＾　　　　　　　＾

正解は

６　３　１　３　６　９　　…　最大10である。
　　　＾　　　　　＾

さらに２つに分ける場合だと、78を受けて

６　３　１　３　６　９　　…　最大19
　　　　　　　　　＾
一方、正解は

６　３　１　３　６　９　　…　最大15
　　　　　　　＾

73の日本語がわけわかんないのは言うまでもないけど
もし､これがグリーディーなアルゴリズムなら
>お、間違ってると指摘されたよ。
>かなり自信あったんだが。
>他の人はどう思う？
の発言は痛すぎる（ｗ
とりあえず､書き込む前に考えないとね

オセロやチェスは総当りでもOKだろうけど、
将棋ってこういう考えかたしないと、
とてつもない量の計算になるよなぁ

>>81
かなりずれてると思われ。

それじゃソースあげておきます。
申し訳程度のコメントしかついていません。
改行少なくするため、つめて書いていますが許してください。
せっかく公開するんだから、もしバグがあったら、是非教えてくださいね

#include <stdio.h>

// 個数
#define N 10
// セパレートの数
#define SEPARATOR 3

// 与えられる配列
const int array[N]={15,3,7,6,10, 4,13,2,3,6};

#define MAX(a,b) (((a)>(b))?(a):(b))

// 表のセルにあたる構造体
typedef struct
{
// この地点の最適の解
int sol;
// その地点から何個か
int num;
} cell;

int main(void)
{cell solutions[N][SEPARATOR+1];int i,j,s,sum;

// 表の後ろの方から順に埋めていく
for(i=N-1;i>=0;--i)for(j=0;j<SEPARATOR+1;++j)
{solutions[i][j].num=0;for(sum=0,s=i;s<N;++s)
{sum+=array[s];
if(j==0 || i==N-1 || solutions[i][j].num==0
|| (s!=N-1 && solutions[i][j].sol>MAX(sum,solutions[s+1][j-1].sol)) )
{if(j==0 || i==N-1)
// １行目か、もしくは最終列ならば、処理無し
solutions[i][j].sol=sum;else
// より良い解決方法を記録する
solutions[i][j].sol=MAX(sum,solutions[s+1][j-1].sol);
solutions[i][j].num=s-i+1;}}}

// デバッグ用にテーブルを表示
for(j=0;j<SEPARATOR+1;++j){for(i=0;i<N;++i)
printf("%2d,%2d ",solutions[i][j].num,solutions[i][j].sol);
printf("\n");}
printf("\n最大の和:%d\n分割方法:",solutions[0][SEPARATOR].sol);
for(i=0,j=SEPARATOR;j>=0 && i!=N;--j){
printf("[%d個] ",solutions[i][j].num);i+=solutions[i][j].num;}
return 0;}

あらら間違ってたか。
＞78
ありがとう。

ゲームの思考ルーチン作ってるとき「あこりゃ巡回セールスマン問題だ」って
気付いたことがあった。時間なかったからほっぽったけど。

>「あこりゃ巡回セールスマン問題だ」って気付いたことがあった
巡回セールス問題の最適解を求めるアルゴリズムはないです

最適解以外は意味無いとでも思ってる？

>>86
多項式のオーダで求めるアルゴリズムがない、ね。
>>85はそれは分かってて時間がないから放置したんだと思われ。

>>81
将棋もオセロもどう考えても総当りじゃ無理だぞ。

将棋とかオセロとかだと幅優先探索でやるのかな？
ゲームによっては探索する深さが指定できるでしょ？
深読みすれば強いＡＩってことで。

ちゃんとした強いＡＩにしたければニューラルネットとかＧＡとかを使うのかなぁ？

GAだって（笑）

>>90
　まあ、将棋とかオセロは基本的には幅優先探索。
　あとは、いかに枝刈りするかという話しになります。

　GAって遺伝的アルゴリズムのこと？
　ニューラルネットとかじゃ、現状ではまっとうなゲームプレイヤー
は作れてないと思います。

関係無いけど、チェスの世界チャンプに勝ったスパコン（ディープブルーだっけ？）
あれって、動的計画法？それとも、総当り？

http://www-6.ibm.com/jp/rs6000/resource/deepblue/
こんなの見つけたけど、どうなんだろう？
棋譜を参照にするってことは枝切りしてるのかな？序盤と終盤だけは、
それ以外は総当りで

>動的計画法？それとも、総当り？
２択かい？（笑）

>>93
スレ違いなので、下げます。

えっと・・・。総当りという言葉をどういう意味で使ってる
かわからないけどミニマックス法、αβ法、静的評価関数とい
ったあたりの話しは大丈夫？知らなかったら検索かけてみて。

　序盤では人間が定石を使うような感じで棋譜を利用する。
　こういう探索問題で一手深く読むためには、下手すると何
十倍という時間がかかってしまうのね。で、終盤検索かけて
るときに、「この局面になったらもう勝ちだ」とか、「この
局面になったら負けだ」とかいう情報があると、その局面に
ついては最後まで読んだことになるから、すごく効いてくる
らしいのね。
　コンピュータの強みは物量作戦だっていう事ですね。

ぶり返すようで悪いんだけど..
>>34の
[15,3]、[7,6,10]、[4,13]、[2,3,6]
って答えはあってるの？
>>8のアルゴリズムで解くと
[15,3]、[13,4]、[10,6,2]、[7,6,3]
ってなるけど。各箱の数値の合計の最大値が
最小になるように仕分けるんだよね？

>>97

>>16 で 1 が数字の順番は入れ換えちゃだめ、って言ってるから
>>34 の答えでたぶん合ってるんじゃなかろうかと。

すいません…
勘違いしてました…。

>>99
なんで100にも届こうか問いスレなのに、
いまだに問題を理解してないやつが居るわけ？

>>93
動的計画法でゲームのAIは大抵無理でしょう。つーか理解してないでしょ。
総当たりのうち、どれだけ効率的に枝切りをするかという問題じゃないの？
それとももっとエレガントな方法があるのかな？

どうでもいいけど、課題教えてスレが、なぜか優良スレになってしまったのはどうして？

>課題教えてスレが、なぜか優良スレになってしまったのはどうして？
1がコテハンじゃなかったから

動的計画法は奥が深いから

誰か他の問題もあげてくれ
マージソート､クイックソートも動的計画法でいいんだよね？
分割統治法っていうんだっけ？

トリッキーの１が出てきたから。

>>103
分割統治法というのは、動的計画法とは正反対の手法じゃないの？
一般的なバックトラックみたいな。マージ／クィックソートも。

アルゴリズム板が無いっていうのがそもそも間違ってるんだよな。

でもそんなに頻繁にアルゴリズムの話題出てないし

グリーディーアルゴリズムって？

試行錯誤によって解を得ようとするアルゴリズム。別名力技。
かかる計算量などを一切無視して作られるアルゴリズム。

グリーディー：貪欲な

>かかる計算量などを一切無視して作られるアルゴリズム
嘘の情報流すのやめようよ

>>109
ゴメ、俺はそう信じてた。>>107さん、嘘らしいですごめんなさい

簡単なので良かったら（高校数学レベル）

1からnまでの数字を1回だけ使って並べて、n桁の数字を作る。
出来る数字を、辞書的に並べた場合、m番目に来る数字は何か

mとnは定数

スマヌ、日本語ｵｶｼｲ

n桁の数字＞n桁の数
出来る数字＞出来る数

3だったら、
123
132
213<-
231
312
321
って事？

あ、ゴメ、n=3、m=3の場合

基数ソートでいいのかな？
高校数学ってどこらへんが？

nは最大でも9。そのときでもmは最大で362800。
ってことは、一回テーブル作っとけば充分じゃん。

>nは最大でも9
かわいそう・・・
大学卒業してないみたい

>>113
そういうことです。

>>116
君の頭の中では十六進数は無いんだね

高校数学って16進習ったっけか?

高校じゃ習わないな、良く考えたら
っていうか、ム板来てて16進解らないんならホントかわいそう

二進数は中学で習う

>>117
高卒プログラマですが何か？

階乗使って上のケタから決定していくのかな。

16進がありならnは数学の立場からすれば何でもいいんでしょうね。
たまたまコンピュータの都合で16進がポピュラーになっただけだから。

なんで１６にこだわってるんだろ
馬鹿ばっかり

>>124=116
16はnの例だろ。

あげ

n進法は中学で習ったんじゃないですか？今はしらんです。

習った覚えがあるけど10をこえた記憶は無い
そろばんが５進数＋２進数とかやってた記憶がある

10超えようが超えまいが関係ない。
A-Fを使うのは表現（符号化）の問題なので、
n進法とは別の問題

>>1
動的計画法の練習問題としていい問題ですね．
ただし，k が大きくて，i_1, i_2, ... , i_n がさほど大きくなければ，
目的関数の値の上界と下界を求めて，目的関数の値に関して２分探索かけた方が
早い？（自信なし）

ちなみに与えられた数の入れ替えを許すと Knapsack や Bin Packing 系の
NP困難問題になる．まあ，その場合でも擬似多項式時間の，動的計画法の
アルゴリズムはある．そっちが宿題だったら院生レベルかな．

「自信なし」と書きましたが，「確信」に変わりました．

ある自然数 T について，答えが T 以下であるか否かを判定するのにかかる
時間は O(n)．２分探索を行うならば，答えが T 以下になるかどうかの判定を
O(log σ) 回のを行えばよい（ただし，σ = i_1 + i_2 + ... + i_n）．
よって，全体の計算量は O(n log σ)．

i_1, ... , i_n として，桁数が kn より大きい数を扱うことは通常はないと
思われるので，O(n log σ) は，O(kn^2) より十分速いと思われる．

なお，２分探索による解法の時間計算量を調べる際，上界に σ，下界に 0 という
自明な値を用いたが，自明でない上界，下界を使えば，実際はもっと速いだろう．

結論：
>>1 の問題は動的計画法の例題としては良くできている．
でも，この問題を解くのに本当に動的計画法を使うべきではない．

緊急浮上

>>131
ある自然数Tをどうやって決めるのか。
それが正しくなかった場合どのように試行錯誤するのか。
君の説明では全然解らないぞ

ソースコードさらせ