old_contents: # Time:  O(n)
  # Space: O(n)
  #
  # Given n items with size A[i], an integer m denotes the size of a backpack. 
  # How full you can fill this backpack? 
  #
  # Note
  # You can not divide any item into small pieces.
  #
  # Example
  # If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, 
  # so that the max size we can fill this backpack is 10. If the backpack size is 12. 
  # we can select [2, 3, 7] so that we can fulfill the backpack.
  #
  # You function should return the max size we can fill in the given backpack.
  #
  class Solution:
      # @param m: An integer m denotes the size of a backpack
      # @param A: Given n items with size A[i]
      # @return: The maximum size
      def backPack(self, m, A):
          # write your code here
          d = [[False for j in xrange(m+1)] for i in xrange(2)]
          result = 0
          d[0][0] = True 
          
          for i in xrange(1, len(A) + 1):
              d[i%2][0] = True 
              for j in xrange(1, m+1):
                  d[i%2][j] = d[(i-1)%2][j]
                  if j >= A[i-1]:
                      d[i%2][j] = d[(i-1)%2][j] or d[(i-1)%2][j-A[i-1]]
                  if d[i%2][j]:
                      result = max(result, j)
                      
          return result
  
new_contents: # Time:  O(n*m)
  # Space: O(m)
  #
  # Given n items with size A[i], an integer m denotes the size of a backpack. 
  # How full you can fill this backpack? 
  #
  # Note
  # You can not divide any item into small pieces.
  #
  # Example
  # If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, 
  # so that the max size we can fill this backpack is 10. If the backpack size is 12. 
  # we can select [2, 3, 7] so that we can fulfill the backpack.
  #
  # You function should return the max size we can fill in the given backpack.
  #
  class Solution:
      # @param m: An integer m denotes the size of a backpack
      # @param A: Given n items with size A[i]
      # @return: The maximum size
      def backPack(self, m, A):
          # write your code here
          d = [[False for j in xrange(m+1)] for i in xrange(2)]
          result = 0
          d[0][0] = True 
          
          for i in xrange(1, len(A) + 1):
              d[i%2][0] = True 
              for j in xrange(1, m+1):
                  d[i%2][j] = d[(i-1)%2][j]
                  if j >= A[i-1]:
                      d[i%2][j] = d[(i-1)%2][j] or d[(i-1)%2][j-A[i-1]]
                  if d[i%2][j]:
                      result = max(result, j)
                      
          return result
  
subject: Update backpack.py