Hatena Blog Tags
はてなブログ トップ
動的計画法
このタグでブログを書く
言葉の解説
ネットで話題
関連ブログ

動的計画法

(サイエンス)
【どうてきけいかくほう】

1957年，Bellmanによって提案された多変数最適化問題を解くための手法．
目的関数に再帰性 (可分性) と単調性があり，制約式が逐次的であるとき，原問題をある部分問題群に埋め込んで，各部分問題の最適値を定義し，相隣る問題の最適値間の関係式 (再帰式) を導く．これを逐次解いて，最後に与問題の最適解を求める方法である．解法の効率化のためには，決定変数，状態変数，評価関数などの選択・設定に個々の創意工夫を要する．

(「OR用語辞典」より)

*リスト::数学関連

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。
地上の洞窟•3ヶ月前

【Ruby】最小個数部分和問題を動的計画法で解く

1 2 3 4 5ここにある数字を好きに組み合わせて足していき、目標となる値を作れるか？ そんな問題を「部分和問題」という。9を目標の数とする場合 1, 3, 5 2, 3, 4 4, 5 目標の数となる組み合わせはいくつかあり、その中でも4, 5が手っ取り早い。 このような 「目標の数を作るために、必要な数の個数は最小で何個か？」 というのを考えるのが「最小個数部分和問題」である。これを「動的計画法」を用いて効率よく解く方法を解説する。 動的計画法を使う 1. 表を用意する 2. 初期値を埋める 3. 各マスの計算 実装 個数制限あり 個数制限なし 個数制限あり・一次元配列 個数制限なし・一…

#Ruby#動的計画法#部分和問題

関連ブログ

地上の洞窟•3ヶ月前

【Ruby】「編集距離」を動的計画法で計算する

yukari yukkuriある二つの文字列がある。 この二つを全く同じ文字列にするのに、一文字ずつの挿入・削除・置換を行う。 それらの操作は最小で何回だろうか？ このような「最小操作回数」のことを「編集距離」*1と呼ぶ。バージョン管理や分析、つまりは差分や類似度を求める際などに用いられるらしい。 これを動的計画法を使って簡単に求める方法を記す。 編集距離の計算 動的計画法を使う 1. 表を用意する 2. 初期値を埋める 3. 各マスを計算していく 実装 編集距離の計算 まず、実際の最小操作回数を見てみる。 yukari yukkuri 1. "a" を "k" に置換 yukari → yu…

#Ruby#動的計画法#編集距離
地上の洞窟•9ヶ月前

【Ruby】動的計画法を考える③「部分和問題」

10になるカードの組み合わせはある？数字の書かれたカードが並んでいる。 この中から好きなカードを選び、書かれた数字の合計が10になる組み合わせは存在するか？ このような「部分和問題」を「動的計画法」を使って効率よく解く方法を考える。 部分和問題を考える 実装 ループ ビットDP →②ナップサック問題 部分和問題を考える 部分和問題はナップサック問題の一種として考えることができる。 ナップサック問題では要素(荷物)に 重さ 価値 という二つの属性があったが、部分和問題では「重さ=価値」として扱える。また、動的計画法にて計算をメモする場合、通常のナップサック問題では memo[i][j] = v …

#Ruby#動的計画法#DP#部分和問題
地上の洞窟•9ヶ月前

【Ruby】動的計画法を考える②「ナップサック問題」

どれを持ち帰る？冒険者が旅の途中、たくさんの宝物を見つけました。 しかし、持ち帰れるのは8kgまでです。 持ち帰る宝物の価値が最も高くなるには、どれを持ち帰ればいいのか。 それを知るべく我々はアマゾンの奥地「動的計画法」の奥地へ向かった・・・。 ナップサック問題を考える bit全探索 実装 動的計画法 実装 メモ化再帰 ループ ループ(一次元配列メモ) 選択した要素の取得 選択状況を記録 メモから逆算 →その①「フィボナッチ数列」 →その③「部分和問題」 ナップサック問題を考える 冒頭に挙げたような問題は「ナップサック問題」と呼ばれる。 組合せ最適化問題の一つだ。問題を解くには、各要素を選ぶo…

#Ruby#動的計画法#DP#ナップサック問題
地上の洞窟•9ヶ月前

【Ruby】動的計画法を考える①「フィボナッチ数列」

全探索では解けないような難しい問題を解くのに欠かせない「動的計画法」について考える。 動的計画法とは 「フィボナッチ数列」の計算 愚直な計算 動的計画法を使う計算 実装 Non-DP DP(メモ化再帰) DP(ループ) →②「ナップサック問題」 動的計画法とは そもそも動的計画法が何なのかをざっくり言うと、 「計算結果をメモしながら解くと、効率よく問題を解ける」 という、問題を解くための指針である。「それのどこが動的で計画なのよ？」と思うだろう。 正直、名前だけではイメージは付きにくい。 動的は「その時に決まる」という意味であり、 「その時その時に計画する」というのはもはや無計画に見える。"D…

#Ruby#動的計画法#DP
ルクの競プロ部屋•1年前

競プロ精選 100 問 by C++<動的計画法：ナップザック DP またはその亜種>

はじめに 今回は、39から45の7問解きました！ ちゃんとcopilotなしでやりました(当たり前) 39 JOI 2011 予選 4 - 1 年生 問題はこちらです！ 問題文↓ 数列が与えられ、その間に+か-を入れていく 途中、「0未満になる」または「20を超える」ことのない式は何通りか これは、縦N-1(数列の間の個数)、横21(0を含む)のDPを作成しました もし、0未満、20を超えることがでたらDPに書き込まないようにすれば終わりです コードはこんな感じです #include <bits/stdc++.h> using namespace std; #define rep(i, n) …

#競プロ#動的計画法#精選100問
walkingsdbgの日記•1年前

長期投資における投資比率の最適化(1/2)

はじめに 問題設定 再帰式の導出 動的計画法による最適解の導出 まとめ 参考文献 はじめに 新NISAをきっかけに投資を始めようと思い立ったのですが、「どの金融商品にどれくらいの比率で投資すればよいのか」が分からないので、投資を最適化問題として定式化し、その最適解を求めることでこの比率を決めます。 問題設定 投資比率の決定を最適化問題として表すには、まず「何を最大化するのか」を決める必要があります。これを目的関数と呼びます。投資なので「最終的な資産の期待値」を目的関数とするのが自然に感じますが、これは破産リスクの高い投資に繋がります。例えば、以下のギャンブルを考えます。 所持金10万円 コイン…

#投資#資産運用#最適化#動的計画法
stosasa’s blog•2年前

atcoder ABC 318 D - General Weighted Max Matchingの勉強

atcoder.jp・参考 Editorial - THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318） 「bitDPで巡回セールスマンを解く」の解説がよくわからなかったのでさらに解説【python実装】 - Qiita bitDP（集合を用いたDP）について - D言語で競プロ ・説明 参考記事の1つ目をPythonで実装した。この問題はbitDPを使って解く。bitDPについては参考記事2，3を参考にした。 集合bに含まれていない頂点を追加してDPを更新していく。コードの説明は下の実装でコメントアウトしている。 …

#Python#AtCoder#AtCoder Beginner Contest#bitDP#動的計画法
stosasa’s blog•2年前

AtCoder Beginner Contest 214 C - Distributionの勉強

atcoder.jp・参考： DPのやり方はDistribution [AtCoder Beginner Contest 214 C] - はまやんはまやんはまやん ダイスクラ法はEditorial - AtCoder Beginner Contest 214を参考にした。・説明： この問題は2つやり方があり、DPとダイスクラ法でできる。 注意点として、DPでは円上なので例えばN=4のとき4,3,2,1が最適解の場合もあるので2周する必要がある。 詳しい説明はコメントアウトしている。・DP n=int(input()) s=list(map(int,input().split())) t=li…

#Python#AtCoder#AtCoder Beginner Contest#動的計画法#競技プログラミング
stosasa’s blog•2年前

atcoder ABC 317 D - Presidentの勉強

atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 参考にも書いてあるが、ナップサック問題のDPと同じように解ける。dp[n]はn議席獲得するために必要な鞍替えさせる最低限の人の数である。 今回は鞍替えさせる人数をコストwと見てこれを最小にすることを考える。コストwはX[i]>Y[i]のとき鞍替えさせる必要がないので0、X[i] #入力。 n=int(input()) X=[] Y=[] Z=[] s=0 for _ in range(n): x,y,z=m…

#AtCoder#AtCoder Beginner Contest#Python#動的計画法