Backpack II Template

https://www.lintcode.com/problem/backpack-ii/description

背包问题以系列的模板

class Solution:
    """
    @param m: An integer m denotes the size of a backpack
    @param A: Given n items with size A[i]
    @param V: Given n items with value V[i]
    @return: The maximum value
    """
    def backPackII(self, m, A, V):
        # write your code here
        n = len(A)
        dp=[(m+1)*[0] for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                dp[i][j] = dp[i-1][j]
                if j >= A[i-1]:
                    dp[i][j] = max(dp[i][j],dp[i-1][j-A[i-1]] + V[i-1])
        
        res = 0
        for j in range(1,m+1):
            res = max(res,dp[n][j])
        return res