Dynamic Programming Practice

dp.py

# coding: utf-8
# Dynamic programing: knapsack problem.
# Rewrote the program in the webpage below in Python.
# 動的計画法（ナップサック問題）
# 下記のサイトのコードを Python にて書き直した。
# reference: http://dai1741.github.io/maximum-algo-2012/docs/dynamic-programming/

VALUES = [15, 3, 1, 8, 2, 4]
WEIGHTS = [11, 2, 3, 5, 1, 4]
MAX_WEIGHT = 15

def depth_first():
  def value(item, available_weight):
    max_value = None
    if (item == len(VALUES)):
      max_value = 0
    elif (WEIGHTS[item] > available_weight):
      max_value = value(item + 1, available_weight)
    else:
      max_value = max(
        value(item + 1, available_weight),
        value(item + 1, available_weight - WEIGHTS[item]) + VALUES[item])
    return max_value
  return value(0, MAX_WEIGHT)  # Starts from item #0 with empty knapsack.

def memo():
  cache = {}
  def value(item, available_weight):
    if (item, available_weight) in cache:
      return cache[(item, available_weight)]
    max_value = None
    if (item == len(VALUES)):
      max_value = 0
    elif (WEIGHTS[item] > available_weight):
      max_value = value(item + 1, available_weight)
    else:
      max_value = max(
        value(item + 1, available_weight),
        value(item + 1, available_weight - WEIGHTS[item]) + VALUES[item])
    cache[(item, available_weight)] = max_value
    return max_value
  return value(0, MAX_WEIGHT)  # Starts from item #0 with 0 empty knapsack.

def recurrence():
  cache = {}
  for i in reversed(range(len(VALUES))):
    for j in range(MAX_WEIGHT):
      if (WEIGHTS[i] > j):
        cache[(i, j)] = cache.get((i + 1, j), 0)
      else:
        cache[(i, j)] = max(
          cache.get((i + 1, j), 0),
          cache.get((i + 1, j - WEIGHTS[i]), 0) + VALUES[i])
  return max(cache.values())  # Returns the maximum value in cache.

if __name__ == '__main__':
  print(depth_first())
  print(memo())
  print(recurrence())