2018-09-24から1日間の記事一覧

動的計画法3 最長共通部分列

動的計画法シリーズ,3個目の例題です.前回のエントリの最後で説明したステップ通りに問題を解いていきたいと思います.今回の問題も有名な問題で,”最長共通部分列問題”と呼ばれるものです.問題の定義は,,, 問題定義 二つの与えられた文字列に対して…

動的計画法2 コイン問題

動的計画法シリーズ,2個目の例題です.この問題も結構有名な問題らしく,ググるといろいろ出てきます.今回は再帰を使ってこの問題を解く方法を考えて,そこから動的計画法の表を作ってみたいと思います. 問題定義 額面が C1, C2, ... , Cm のコインを使…

動的計画法1 ナップザック問題

引き続き,動的計画法です.今回はフィボナッチ数の問題よりも少し難しくなりますが,動的計画法のありがたさがよくわかる例かと思います.取り上げる問題は,有名な "ナップザック問題" です.問題は, 重さが wi, 価値が vi であるような n 個の品物がある…