ナップザック問題
久しぶりにナップザック問題書いてみたら思いの外時間がかかって辛かった
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 = Array.new(N).map { Array.new(N, INF) } def dfs_memo(i, w) return 0 if i == N b = dfs_memo(i + 1, w) a = w - ITEMS[i][0] >= 0 ? dfs_memo(i + 1, w - ITEMS[i][0]) + ITEMS[i][1] : 0 $memo[i][w] = [a, b].max end p dfs_memo(0, W) # => 7 # dp $dp = Array.new(N + 1).map { Array.new(W + 1, 0) } def solver (1..N).each do |i| (1..W).each do |j| a = $dp[i-1][j] b = j >= ITEMS[i-1][0] ? $dp[i-1][j-ITEMS[i-1][0]] + ITEMS[i - 1][1] : 0 $dp[i][j] = [a, b].max end end end solver p $dp[N][W] # => 7