適当にa[i−5]からa[i]の和を全て出力します。Tagsから選んで解いてみましょう!!DP(DynamicProgramming)漸化式(のようなもの)を立てて様々なものを求めるアルゴリズムです。次のような問題を考えてみましょう。ナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます:選んだ品物の価値の合計をできるだけ高くする。価値の合計の最大値を求めてください。空白区切りで1行に与えられます。空白区切りで与えられます。出力:価値の合計の最大値を1行に出力してください。制約:1≤N≤1001≤vi​≤10001≤wi​≤10001≤W≤10000この問題は、どのようにして解けばいいのでしょうか。DPを知らないとどこから手を出せばいいのかもわからないと思います。理論、考え方では、実際にDPを使って解いていきましょう。DPとは、漸化式を作ると言いましたが、これは実際には主に配列を用いて表現します。簡単な例を言うと、dp[i+1]=max(dp[i]+cost[i],dp[i])のような形です。このように式を作るには、まずなにを式にするのかが大切になります。これは問題を実際にたくさん解いて身につけていきましょう。この問題では、配列dp[i+1][w]をiまでの重さの総和がw以下で最大化した価値であるとします。すると、dpの漸化式は以下のように考えることができます。w>=w[i]のときdp[i+1][w]=max(dp[i][w−w[i]]+v[i],dp[i][w])w<w[i]のときdp[i+1][w]=dp[i][w]少し解説します。上の式はi番目まで価値を最大にとってきたときに、i+1番目において、品物をナップザックに入れられる状態を表しています。wがwi​よりも大きいときには、w−w[i]までの重さで価値を最大化させてきたナップザックにw[i]の重さの品物を入れてwまでの重さで価値を最大化させた状態が作れますよね?さらに追加できるときに追加したほうが価値が大きくなるかどうかを判断するために、max関数を用いて価値を最大化させています。同様にwがw[i]よりも小さいときにはナップザックに追加できないので(追加するとi+1番目での重さの総和がwを超えてしまう)、そのような場合にはそのままの価値を受け継ぎます。ここで、漸化式を使うには初期値が必須です。DPを用いる時には忘れないようにしましょう。今回の場合は、初期値はdp[0][0]=0と定めることができます。N個を使ってWまでの重さで価値の最大化を行えばいいので、求めるのはdp[N][W]であることがわかります。実装プログラムにすると、次のようになります。実行できるように変数名を少し変えています。dp[i][w];print(dp[N][W])このように、i番目とi+1番目で関係性が見えてきそうな問題には、DPを使ってみましょう!実はこの問題はAOJで実際に解くことができるとても有名なナップザックDPという問題です!理解できたら解いてみましょう。Tagsから解いてみましょう。DPにはこのような基本的なものからとても難しいものまでたくさんの種類があります。†完全に理解した†方は、他のDPも勉強してみましょう!さいごにレベルアップするためのアルゴリズムや考え方を3つ紹介してきましたが、いかがでしたでしょうか?紹介したいアルゴリズムはもっとあるのですが、長くなりそうなので絞って紹介しました。わかりにくい点がありましたらコメントやTwitterなどで質問してください。自分も勉強中なので間違っている点があるかもしれません。そのような場合はコメントやTwitterで馬鹿にしてください...もっといろいろなものを知りたい、より詳しく知りたいという方は、ググってみたり、蟻本[1]を買ってみるといいと思います。明日、12月17日はmazreanくんの記事です。お楽しみに!表紙に蟻がいるので、蟻本と呼ばれています。多重スリーブの世界と,各種進捗報告。