読者です 読者をやめる 読者になる 読者になる

ナップザック問題

久しぶりにナップザック問題書いてみたら思いの外時間がかかって辛かった

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