「大きなナップサック」問題解説＆最終成績発表～神級到達者30名！ #アルゴリズム｜CodeIQ MAGAZINE
出題者Ozyさんによる「大きなナップサック」問題の解説記事です。 最適解を導くためのアルゴリズムについてわかりやすい図解付きで説明してくれています。 そして、神級到達者はなんと30名！ニックネームを公開していますよ！ by CodeIQ運営事務局 はじめに 出題者のOzyです。大きなナップサック問題解説です。 今回解説するのは、ナップサック問題の中でも“単一制約の01ナップサック問題”と呼ばれる種類のものです。ちょっと長いですから、今後は単に“ナップサック問題”と表記します。ナップサックに入れる品物には、値段と重量の2要素があり、重量が“制約”に相当します。また、品物1つひとつについては、ナップサックの中に、入れる／入れないという2つの状態がありますので、これは0と1で表現できることから、“01”と呼ばれています。 大きめのナップサック問題を解く場合に用いられる手法として有名なものは、動的
数え上げ問題集 ver.0 - tozangezan's diary
数え上げ問題集 数え上げの問題をある程度まとめます。といっても多すぎて面倒なので、まとまって存在するものはリンクを張ります。 また、検索の都合上「答えを1000000007で割った余りを求める」以外の形式の数え上げは見落とされがちなので、そこらへんは割り切ってください。 まとまって存在するリスト(数え上げをたくさん解きたい人用) http://codeforces.com/problemset/tags/combinatorics 数え上げばっかり集めてあります http://community.topcoder.com/tc 多すぎる上ローカルに保存してなくて調べるのが面倒なので、自分で調べてください。 参考までに、感じる難易度をTopCoder Div1の点数に換算して書いておきます。 良問には☆をいくつか付けます。 AOJ 2333 (500) ☆ AOJ 2335 (650) AO
簡単そうで難しい組合せ最適化
簡単そうで難しい組合せ最適化 簡単そうで難しい組合せ最適化 高校生，高専生，大学学部生の皆さん 私たちの研究室では，組合せ最適化（離散最適化）という ものを研究の対象にしています．これは離散数学の問題で すが，私たちの身近なところにも現れています．ここでは 組合せ最適化問題の例を挙げて，その解決に向けた研究に ついて説明いたします 京都大学工学部情報学科 数理工学コース 京都大学大学院情報学研究科 数理工学専攻 離散数理分野 長方形詰め込み問題 最初にパズルのような問題を紹介しましょう．左の図のようにいくつかの長方 形が与えられ，これらを入れ物に重ならないように詰めます．このとき，右の 図のように詰めた結果の高さをできるだけ低くすることがこの問題の目的です． １ ２ ３ ７ ６ ４ ５ ６ ８ ９ ２ ８ ５ ７ ４ ９ １ ３ 与えられた長方形 入れ物 詰めた
Algebraic DP: 動的計画法を書きやすく
PFI社内セミナー（2012/11/22）で動的計画法の新手法・代数的動的計画法について発表した際の発表資料です。発表の模様はこちら： http://www.ustream.tv/recorded/27196711
DP特集
プログラミングコンテスト勉強会での発表スライド。2012年国内予選出場者向けの、グラフとDPを用いて解く問題の解説
DPの話 (追記) - aizuzia
前回の記事に対してみやむーさんから素晴らしい反響を頂いたので、こちらにレスポンスする形で追記してみます。 そもそも前回の「DPの話」は、こちらのエントリと内容が全く同じなのでした。全然気付いてなくてごめんなさい・・・。 ループのメリットとメモ再帰のメリット 「メモ再帰のメリットは計算が遅延的に行われること」とのことでした。メモ再帰では、「最終的に求めたい状態には絶対に遷移し得ないノード」への計算は行われません。そのようなノードが数多くある問題では、メモ再帰が速くなりうる。なるほど。 似たようなことがループでは絶対できないというわけではありません。配るDPにおいて、配る元のノードの値が初期値 (最短経路だったら inf とか、経路数だったら 0 とか) のままだったら、配っても意味が無いのでやめる。このような枝刈りを加えると、「初期状態から絶対遷移しないノードから」の計算は行われません。 が
DPとかメモ化再帰とか(2) - komiyamの日記
Competitive Programming Advent Calendarでtayama0324さんが素晴らしい記事を書いておられました。なので自分もそれに触発されて、以前書いた記事の続きを書いてみました。以下はtayama0324さんの記事を読んでいることを前提に話をします。 DPのメリットとメモ化再帰のメリット 基本的にはtayama0324さんが触れているメリットでつきていると思うんですが、自分は次のようなメリットもあると考えています(本筋から離れるだけなので、tayama0324さんも知っていた上で敢えて書かなかっのだと思います)。 DPのメリット 配列の再利用でメモリが節約できることがある。 データ構造を工夫しての高速化が書きやすい。 メモ化再帰のメリット 評価が遅延的に行われる。 ひとつずつ説明します。 配列の再利用 これは非常によく知られていることだと思います。配列ではあ
Reinforcement Learning in R: An Introduction to Dynamic Programming | statalgo
Reinforcement Learning is an approach to learning that attempts to maximize a cumulative reward based on a set of actions and states. The techniques are very popular within operations research and control theory. It does not fall under the traditional paradigms of supervised or unsupervised learning because correct inputs/outputs are never provided. The algorithm is instead presented with some not
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
ループのない有向重み付きグラフにおける最短経路問題 - 純粋関数型雑記帳
昨日、問題Dにダイクストラを持ち出す必要がないことが分かって 驚愕した訳であるが、これをもうちょっと一般的に考えると、 ループのない有向重み付グラフにおける最短経路問題が 再帰+メモで解けることが分かった。 再帰的定義は、あるノードからのゴールまでの距離である。 これがすべてのノードにつき高々一回計算されれば良いので 非常に効率よく計算できる。 このアルゴリズムでは、全ノードからのあるノードへの距離が分かる。 ダイクストラ法ではあるノードから全ノードまでの距離が求まるわけであるが、 グラフの向きを逆にするとこれらは等価であることが分かる。 そういうわけで、グラフにループがなければこれからは ダイクストラは使わないことにする。 ダイクストラは効率の良い実装をしようと思うと なんだか色々と引っかかるところがあるのだ。 コードを持ち込むと言う手もあるが、 タイピング速度が遅いのであんまり紙から書
動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし（寅年）の日記
組み合わせ最適化の手法として「動的計画法」というモノがあります。 wikipediaから抜粋 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP） コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法 一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。 ナップサック問題と動的計画法 動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。 こんな感じの問題です。 今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各
アルゴリズムイントロダクション15章 動的計画法
Mar 1, 2009Download as PPT, PDF71 likes24,189 views
ALGORITHM NOTE ナップザック問題 Knapsack Problem
大きさ w と価値 v を持った品物が N 個あり、これらを大きさ W のナップザックに入れたいとします。このとき、大きさの合計が W を超えず、価値の合計が最大になるような品物の組み合わせを求めたい。これがナップザック問題です。各品物を「選択する」か「選択しない」かの組み合わせなので、厳密には0-1ナップザック問題ともいいます。(各品物が複数個ある場合は、0123ナップザック問題と呼ばれます) この問題を力任せで解こうとすれば、N 個の品物を「選択する」か「選択しないか」の全組み合わせを全て調べることになるので、計算効率は O(2N) となります。N が数十個でも、実用的な時間では計算できません。 品物の大きさ w、ナップザックの大きさ W がともに整数であれば、ナップザック問題は動的計画法により O (NW) の効率で厳密解を求めることができます。 C[i][w] が、大きさ w のナ
動的計画法は再帰で表せ
動的計画法の説明は常に再帰関数で書き表すことにしています．いやゆるメモ化再帰です．参照透過な関数は，同じ引数に対して同じ値を返すので，保存しておけばいいという感覚です．計算量の見積もりも簡単で，引数の異なり数に関数中のループの上限をかければおしまいです．特に再帰で書くことに慣れていれば自明に書けますし，テーブルを使ったDPと違って，ループの順番を意識する必要がありません．このテクニックは学部時代に@ohkuraに教えてもらいました．関数型言語に触れた今でこそ当たり前に見えますが，当時は目から鱗だったのを覚えています． メモ化再帰と不動点に関する@kinabaさんの日記や，プログラミングコンテスト的には@chokudaiさんの記事が参考になります． 今更ですが，ちょっと例で説明します．フィボナッチ数を計算する関数fib(x)は再帰式で，fib(x) = fib(x - 1) + fib(x
DPの話 - aizuzia
この記事は Competitive Programming Advent Calendar のために作成されました。 「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない メモ再帰だと書けるけどループだと書けない、またはその逆 とかいう。 この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人と
DPの練習として良さそうなやつ - kyuridenamidaのチラ裏
いろいろなDPがありますが、これもまとめとくと良いと思ったので。僕はDPは得意ではないですが、それでもスキルアップに繋がったなあと感じた問題をピックアップしておきます。 DPかメモ化再帰か――ループの中で色々場合分けとかしなきゃいけなかったり、順序付けしにくかったりするＤＰは出来るならメモ化したほうがバグ減ったり実装楽だったりします。メモ化再帰は初期化ミスとかが無くて済むので。再帰が深くなりそうだったり、特殊なテクニック(ある区間をまとめて足したりする)とかする場合はやはりDPじゃないとだめですが、大体はメモ化再帰で代用が効きます。ではDP問の紹介。 (ネタバレ注意) 簡単な数え上げタイプ・Kannondou[☆]・A First Grader[★] 最長増加部分列タイプ( O(n log n)解法が存在するのでググったり蟻本とかを読むと良い。 )・ビルの飾りつけ(2007年度JOI春合宿
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
SRM 340, D1, 500-point problem
Sign in - Google Accounts
Optimal substructure - Wikipedia
++knowl;