せでぃのブログ

ブログ初心者おいどんのどうでもいい愚痴やどうでもいい愚痴やどうでもいいマメ知識などを披露するチラシの裏です。

計算を総当たり力押しで解決するのが計算機ということか

DPの話 - aizuzia
追記:突然思いついて順列じゃなくて組合せにしたら計算すぐ終わったは。
動的計画法DPの話を調べてて、ここにあるコイン両替問題を完全自力ヒントなしで解いてみようと思って一から考えて作ってみた。
csny/exchange_problem · GitHub
exchange_problem/main.m at master · csny/exchange_problem · GitHub



全探索で時間かかるけど、意外といけたわ。頭で考えればすぐなんだけどねw
あと、再帰呼出の引数内で差し引きするとわかりづらいので、次からはそれやめよ。
最大要素数は1円X63なので63。
順列数はわからん。最大で6の63乗なんだろうけど、マイナスになって落とせる枝がどれくらいなのかもわからんので、適当に当たりを付けて支払い枚数11枚で切り上げた。硬貨の種類が二進数だったので当たりはつけやすい。

寝室が熱くて、なかなか寝る気にならんよね。