ganmacs https://blog.hatena.ne.jp/ganmacs/ memo-mode https://ganmacs.hatenablog.com/ Ruby アルゴリズム 久しぶりにナップザック問題書いてみたら思いの外時間がかかって辛かった N = 4 W = 5 ITEMS = [[2, 3], [1, 2], [3, 4], [2, 2]].freeze # [重さ, 価値] INF = 10000000 # 全探索 def dfs(i, w) return 0 if i == N b = dfs(i + 1, w) a = w - ITEMS[i][0] >= 0 ? dfs(i + 1, w - ITEMS[i][0]) + ITEMS[i][1] : 0 [a, b].max end p dfs(0, W) # => 7 # memo化 $memo =… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fganmacs.hatenablog.com%2Fentry%2F2014%2F07%2F31%2F224106" title="ナップザック問題 - memo-mode" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-07-31 22:41:06 rich https://ganmacs.hatenablog.com/entry/2014/07/31/224106 1.0 100%