1957年,Bellmanによって提案された多変数最適化問題を解くための手法. 目的関数に再帰性 (可分性) と単調性があり,制約式が逐次的であるとき,原問題をある部分問題群に埋め込んで,各部分問題の最適値を定義し,相隣る問題の最適値間の関係式 (再帰式) を導く.これを逐次解いて,最後に与問題の最適解を求める方法である.解法の効率化のためには,決定変数,状態変数,評価関数などの選択・設定に個々の創意工夫を要する.
(「OR用語辞典」より)
*リスト::数学関連
1 2 3 4 5ここにある数字を好きに組み合わせて足していき、目標となる値を作れるか? そんな問題を「部分和問題」という。9を目標の数とする場合 1, 3, 5 2, 3, 4 4, 5 目標の数となる組み合わせはいくつかあり、その中でも4, 5が手っ取り早い。 このような 「目標の数を作るために、必要な数の個数は最小で何個か?」 というのを考えるのが「最小個数部分和問題」である。これを「動的計画法」を用いて効率よく解く方法を解説する。 動的計画法を使う 1. 表を用意する 2. 初期値を埋める 3. 各マスの計算 実装 個数制限あり 個数制限なし 個数制限あり・一次元配列 個数制限なし・一…
yukari yukkuriある二つの文字列がある。 この二つを全く同じ文字列にするのに、一文字ずつの挿入・削除・置換を行う。 それらの操作は最小で何回だろうか? このような「最小操作回数」のことを「編集距離」*1と呼ぶ。バージョン管理や分析、つまりは差分や類似度を求める際などに用いられるらしい。 これを動的計画法を使って簡単に求める方法を記す。 編集距離の計算 動的計画法を使う 1. 表を用意する 2. 初期値を埋める 3. 各マスを計算していく 実装 編集距離の計算 まず、実際の最小操作回数を見てみる。 yukari yukkuri 1. "a" を "k" に置換 yukari → yu…
10になるカードの組み合わせはある?数字の書かれたカードが並んでいる。 この中から好きなカードを選び、書かれた数字の合計が10になる組み合わせは存在するか? このような「部分和問題」を「動的計画法」を使って効率よく解く方法を考える。 部分和問題を考える 実装 ループ ビットDP →②ナップサック問題 部分和問題を考える 部分和問題はナップサック問題の一種として考えることができる。 ナップサック問題では要素(荷物)に 重さ 価値 という二つの属性があったが、部分和問題では「重さ=価値」として扱える。また、動的計画法にて計算をメモする場合、通常のナップサック問題では memo[i][j] = v …
どれを持ち帰る?冒険者が旅の途中、たくさんの宝物を見つけました。 しかし、持ち帰れるのは8kgまでです。 持ち帰る宝物の価値が最も高くなるには、どれを持ち帰ればいいのか。 それを知るべく我々はアマゾンの奥地「動的計画法」の奥地へ向かった・・・。 ナップサック問題を考える bit全探索 実装 動的計画法 実装 メモ化再帰 ループ ループ(一次元配列メモ) 選択した要素の取得 選択状況を記録 メモから逆算 →その①「フィボナッチ数列」 →その③「部分和問題」 ナップサック問題を考える 冒頭に挙げたような問題は「ナップサック問題」と呼ばれる。 組合せ最適化問題の一つだ。問題を解くには、各要素を選ぶo…
全探索では解けないような難しい問題を解くのに欠かせない「動的計画法」について考える。 動的計画法とは 「フィボナッチ数列」の計算 愚直な計算 動的計画法を使う計算 実装 Non-DP DP(メモ化再帰) DP(ループ) →②「ナップサック問題」 動的計画法とは そもそも動的計画法が何なのかをざっくり言うと、 「計算結果をメモしながら解くと、効率よく問題を解ける」 という、問題を解くための指針である。「それのどこが動的で計画なのよ?」と思うだろう。 正直、名前だけではイメージは付きにくい。 動的は「その時に決まる」という意味であり、 「その時その時に計画する」というのはもはや無計画に見える。"D…
はじめに 今回は、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) …
はじめに 問題設定 再帰式の導出 動的計画法による最適解の導出 まとめ 参考文献 はじめに 新NISAをきっかけに投資を始めようと思い立ったのですが、「どの金融商品にどれくらいの比率で投資すればよいのか」が分からないので、投資を最適化問題として定式化し、その最適解を求めることでこの比率を決めます。 問題設定 投資比率の決定を最適化問題として表すには、まず「何を最大化するのか」を決める必要があります。これを目的関数と呼びます。投資なので「最終的な資産の期待値」を目的関数とするのが自然に感じますが、これは破産リスクの高い投資に繋がります。例えば、以下のギャンブルを考えます。 所持金10万円 コイン…
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を更新していく。コードの説明は下の実装でコメントアウトしている。 …
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…
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…