ナップサック問題

蟻本から：

重さと価値が, の物体n個から、重さの総和がWを超えない部分集合の最大の価値を求める。

解法としてはメモ化か：

def solve(vs, ws, W):

  def max_v(i, max_w, memo = {}):
    if i >= len(vs): 
      return 0
    if (i, w) in memo: 
      return memo[i, max_w]

    if ws[i] > w:
      memo[i, w] = max_v(i+1, w)
    else:
      memo[i, w] = max(max_v(i+1, w), max_v(i+1, w-ws[i])+vs[i])
    return memo[i, max_w]

  return max_v(0, W)

動的計画法：

def solve(vs, ws, W):
  grid = {(i, w):0 for i in range(len(vs)) for w in range(1, W+1)}

  for w in range(1, W+1):
    for i in range(len(vs)):
      if ws[i] > w:
        grid[i, w] = grid.get((i-1, w), 0)
      else:
        grid[i, w] = max(grid.get((i-1, w), 0), grid.get((i-1, w-ws[i]), 0)+vs[i])

  return grid[len(vs)-1, W]        

問題としては有名すぎるほどの動的計画法の解説例。Pythonだとメモ化が（C++などに比べて）簡単なので、どちらの手法が記述として楽か難しいところ。