O(2^n)を全探索

各要素を選ぶか、選ばないかの問題を全探索で解く
O(2^n)かかるが、とりあえずここまでをぱっと作れることが大切

引数にiを使って、i番目の要素を選ぶことを表現する
この書き方よく見るから覚えよう
（個人的にはnを引数で渡して、マイナスしていきたいけど）

# ナップザック問題を再帰で解く
$items = [
  { weight: 2, val: 3 },
  { weight: 1, val: 2 },
  { weight: 3, val: 6 },
  { weight: 2, val: 1 },
  { weight: 1, val: 3 },
  { weight: 5, val: 85 }
]
$n = 6

def recNap(i = 0, u)
  return 0 if i == $n

  tar = $items[i]

  if u - tar[:weight] < 0
    # そのアイテムがいれられないとき
    recNap(i + 1, u)
  else
    # そのアイテムを入れた場合と入れなかった場合の最大
    [
      recNap(i + 1, u - tar[:weight]) + tar[:val],
      recNap(i + 1, u)
    ].max
  end
end

# 部分和問題
$arr = [1, 5, 7]
def canMake(i = 0, m)
  return true if m == 0
  return false if i == $arr.length

  canMake(i + 1, m) || canMake(i + 1, m - $arr[i])
end