# coding: utf-8 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 ''' 动态规划，已m = 10，A = [3, 4, 8, 5]为例： 1. A[0] = 3, c[10] ... C[3] = 3 2. A[1] = 4 - c[10] = max(c[10 - 4] + 4, c[10]) = max(c[6] + 4, c[10]) = 7 - c[7] = c[8] = c[9] = 7 - c[6] = max(c[6 - 4] + 4, c[6]) = 4 - c[4] = c[5] = 4 c[i]表示大小为i的空间的最大容量，对于大小为k的物品，状态转移方程为：c[i] = max(c[i - k] + k, c[i]) ''' capacities = [0] * (m + 1) if A: for i in xrange(len(A)): for j in xrange(m, A[i] - 1, -1): capacities[j] = max(capacities[j - A[i]] + A[i], capacities[j]) return capacities[-1] # medium: http://lintcode.com/zh-cn/problem/backpack/