Backpack

Question

Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?

Thoughts

注意 每个item只能用一次

reference: backpack

dp[i][j]表示A的前i个物品组成size为m的组合的value

init states

dp[0][i] = 0
dp[i][0] = 0

connection function

对第i件物品，最多两个选择

- 放
- 不放

对于dp[i][j]

if j >= A[i-1]
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1])#放与不放，取最大值 
if j < A[i-1]
    dp[i][j] = dp[i-1][j] #不放

final result

Solution

class Solution:
    # @param m: An integer m denotes the size of a backpack
    # @param A & V: Given n items with size A[i] and value V[i]
    # @return: The maximum value
    def backPackII(self, m, A, V):
        # write your code here
        if not m or not A:
            return 0
        dp = [[0 for i in range(m + 1)] for j in range(len(A) + 1)]
        #init states
        for i in range(m + 1):
            dp[0][i] = 0
        for i in range(len(A) + 1):
            dp[i][0] = 0

        for i in range(1, len(A)+1):
            for j in range(1, m + 1):
                if j - A[i-1] < 0:
                    dp[i][j] = dp[i-1][j]
                else:
                    inResult = dp[i-1][j-A[i-1]] + V[i-1]
                    dp[i][j] = max(dp[i-1][j], inResult)

        return dp[len(A)][m]