久しぶりにナップザック問題書いてみたら思いの外時間がかかって辛かった 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] …