めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

2021-07-14から1日間の記事一覧

D - ナップサック問題の解説(その3)

何の話かと言うと enakai00.hatenablog.com上記のエントリーの続きです。はい。 不要な記録をさらに削ぎ落とす(カッコよく言うと刈り込みをする的な何か) 前回の記事の最後に ちなにみ、サブタスク3と言うのは、 かつ という条件があるもので、重さが巨大…

D - ナップサック問題の解説(その2)

何の話かというと enakai00.hatenablog.com上記のエントリーの続きです。はい。 「DPの考え方」に立ち戻る 前回紹介したナップサック問題の解法は、伝統的に言い伝えられて来たものですが、ぶっちゃけ、w0 = 0,...,W のすべて条件を個別に考えるって、気持ち…

D - ナップサック問題の解説(その1)

何の話かというと atcoder.jp(とある事情があって)「DP(動的計画法)の心」がうまく伝わるように説明したいですよねぇ・・・・という会話をしていて、まずは、古典的なナップサック問題を例に取り上げましょうか・・・と思って、適当な過去問を探していて…