アルゴリズムを学習し始めたものの、まだまだなんとなくで進んでいる人のチラシの裏です。
[読んでる本]
アルゴリズムとデータ構造
1はここ↓
https://qiita.com/biscorio/items/918060343eeab6c4570f
動的計画法
課題を部分にわけて、それぞれを選んだ時、選ばなかった時について考えていく方法。
ナップサック問題
かばんの中身にモノを入れよう、ただし貴重品をたくさん入れつつX㎏は超えるな、みたいなやつ。
荷物1 10kg(価値10),荷物2 5kg(価値20),荷物3 13kg(価値5),荷物4 6kg(価値9)とあった時、価値が最大になるようにしつつ、20㎏以内に収めるにはどう組み合わせると良いか、みたいなこと。
考え方
選んだ時、選ばない時を考える。
荷物1を選んだ時、価値10 / 重さ10kgになる。
荷物2を選んだ時、荷物1を選んでいたら価値30 / 重さ15kgになる。
これを、表に埋めていく。
ここでは重さを横軸、選択する荷物を縦にして、それぞれ選んだ場合に価値がどうなるかを見ている。(選ばなかったら0なので気にしなくてOK)
| i/w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ... | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| -(0) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A(1) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 10 | 10 | 10 | 0 |
| B(2) | 0 | 0 | 0 | 0 | 0 | 20 | 20 | 20 | 20 | 20 | 30 | 30 | 30 | 30 | 30 | 30 |
| C(3) | 0 | 0 | 0 | 0 | 0 | 20 | 20 | 20 | 20 | 20 | 30 | 30 | 43 | 43 | 43 | 43 |
| D(4) | 0 | 0 | 0 | 0 | 0 | 20 | 26 | 26 | 26 | 26 | 36 | 36 | 49 | 49 | 49 | 49 |
貪欲法
とりあえず、後先考えずにその場の最善を取り続ける方法。
この方法は、現時点での最適を考えるので、そもそもの問題構成に「良い性質(※)」がないと成立しなかったりする。
課題パターン1：コイン問題
支払いに使うコインを最小にするにはどうするか、というやつ。
500円、100円、50円、10円、5円、1円があるとして、例えば2431円をどうやって支払うか、みたいなこと。
考え方
とりあえず、後先考えなくて良いので、500円で払えるだけ払う。
残った分は、また後先考えずに100円で払えるだけ払う。
これを他のコインでも繰り返す。
どの順序でコインを選択するかが大事。
※良い性質：コイン問題は、実はコインが1円、4円、5円みたいになっていると貪欲法で解けなくなる。8円出すのに5+1+1+1より、4+4の方が少なくて済む。
区間スケジューリング問題
できるだけたくさん仕事ができるようにスケジュールを組む、という課題。
仕事Aは13:00~13:30、仕事Bは13:20～14:00、仕事Cは13:30～14:00、となっていた時、一番たくさん仕事ができる組み合わせを考える。
考え方
仕事というがその実、開始-終了で区切られた「区間」の選択になる。
用意されている区間をどの順序で選択する(しない)かが大事。
終わり時間でソートして、一番早く終わるもの(仕事A)はとりあえず選んでしまう。
仕事Aと、Aと重なるもの(仕事B)を除いて、同じことを繰り返す。
区間の問題は終わり時間でソートするのが良いらしい。