Backpack III

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

这个是Backpack 2的变形。唯一的区别是每一个item可以重复使用多次。

所以在如下的line会有区别

# no repetition
dp[i][j] = max(dp[i][j],dp[i-1][j-A[i-1]] + V[i-1])

#with repetition
dp[i][j] = max(dp[i][j],dp[i][j-A[i-1]] + V[i-1])

在可以重复的时候，会一直到遍历到i-th item因为i-th item本身也可以被使用多次。而不可以重复时候，只能到（i-1) th item因为 i-th item只能被使用一次。

class Solution:
    """
    @param A: an integer array
    @param V: an integer array
    @param m: An integer
    @return: an array
    """
    def backPackIII(self, A, V, m):
        # write your code here
        n = len(A)
        if n == 0:
            return 0
        dp = [(m+1)*[0] for _ in range(n+1)]
        for i in range(n+1):
            for j in range(m+1):
                dp[i][j] = dp[i-1][j]
                if j >= A[i-1]:
                    dp[i][j] = max(dp[i][j],dp[i][j-A[i-1]] + V[i-1])
        
        res = 0
        for j in range(1,m+1):
            res = max(res,dp[n][j])
        return res