JOI予選に向けて - さいどうにっき

こんばんは。

ここ3日ほどAOJをやりまくってる旧長です。

今日はJOIの予選に向けて動的計画法ができるようになろうと思い、ナップサック問題に挑戦しました。

「容量 C のナップサックが一つと、n 個の品物（各々、価値 p_i, 容積 c_i）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」(Wikipediaより)

というものです。

この問題を、動的計画法を使って解くのが今日の課題でした。

以前教わった問題の解法を使ってみたり、ループを書き換えてみたりして、とうとう解くことができました！やったぜ！

浮かれ過ぎとか言わないで放っておいて下さい。しばらくすれば戻ります。

ついでに。

再来週、18日(水)に、ICTAdventCalendarの記事を書きます。僕が作ったオセロについて書くので、よろしくお願いします。