Knapsack

ks.py

import sys

# How to run:
# cat << EOF | python ks.py
# 1
# 10
# 2 6 7 1 5
# 1 1 1 1 1
# EOF
# [(2, 1), (1, 1), (5, 1)]


# 0/1 knapsack solved with dyncamic programming.
# We define an array m[n, W] (n the number of values)
# m[0, w] = 0
# m[i, w] = m[i - 1, w] if w[i] > w else max(m[i - 1, w], m[i - 1, w - w[i]] + w[i])
# In short, either we can't fit the element and we continue with the current
# configuration, either can can fit it and we see if it would advantageous to
# add it with the m[i-1, w-wi] configuration, meaning the previous knapsack
# with reduced capacity of the weight of that element.
# ex.:
# Let's m[i - 1][w] be 8 because we have fitted a 2 and a 6. Our element is 7.
# Our capacity is 8. Wouldn't it be better to throw the 6, and replace with 7?
# For that we look at m[i - 1][w - w[i]] to see with what element 7 could fit.
# Here m[i - 1][w - w[i]] is 2 and 2 + 7 is 9 so let's keep 6 + 2.
# w ...  2   3   4   5   6   7   8
#   --------------------------------
# 6 ...| 2 | 2 | 2 | 2 | 2 | 2 | 8 |
# 7 ...| 2 <-------------------- 9?
def knapsack(w, v, W):
  # The array will contain a tuple with:
  # - the total weight of the element
  # - the list of sacked elements (weight, value)
  m = [[(0, []) for x in range(W + 1)] for y in range(len(w) + 1)]

  # To simplify, make w and v 1-based
  w = [0] + w
  v = [0] + v

  for i in range(1, len(w)):
    for j in range(0, W + 1):
      if w[i] > j:
        # We can't fit our element, just keep the previous weight
        m[i][j] = m[i - 1][j]
      elif m[i - 1][j][0] > m[i - 1][j - w[i]][0] + v[i]:
        # Now we can fit our element, but it wouldn't be a good solution to
        # pop the previous elements and add ours
        m[i][j] = m[i - 1][j]
      else:
        # Popping the previous elements and add ours with those who currently fit
        # seems a good idea
        m[i][j] = (m[i - 1][j - w[i]][0] + v[i], m[i - 1][j - w[i]][1] + [(w[i], v[i])])
  # Returns the last (best) combination
  return m[-1][-1][1]


nbtests = int(sys.stdin.readline().strip())
for i in range(0, nbtests):
  W = int(sys.stdin.readline().strip())
  w = [int(x.strip()) for x in sys.stdin.readline().strip().split(' ')]
  v = [int(x.strip()) for x in sys.stdin.readline().strip().split(' ')]
  print(knapsack(w, v, W))