Backpack

Question

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Example If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 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.

Thoughts

注意 每个item只能用一次

reference: backpack

DP 2d-array的意义

dp[i][j]表示A的前i个物品是否能组成size为j的组合

init states

dp[0][0-m] = False
dp[i][0] = True

connection function

对于dp[i][j], 对应的是A[i-1], size j 对于A[i-1]其实最多有两种选择

- 用A[i-1]
- 不用A[i-1]

取决于j的size

如果j >= A[i-1], 有两种选择 如果j < A[i-1], 只有一种选择，不用A[i-1]

Final result

比m小的最大的dp[len(A)][i]为True的i值

Solution

2d-array O(n*m) memory

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
        if not m or not A:
            return 0
        dp = [[False for i in range(m + 1)] for j in range(len(A) + 1)]
        #init states
        for i in range(m + 1):
            dp[0][i] = False
        for i in range(len(A) + 1):
            dp[i][0] = True

        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:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-A[i-1]]

        for i in range(m, -1, -1):
            if dp[len(A)][i]:
                return i

1d array O(m)

class Solution2:
    # @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
        if not m or not A:
            return 0
        dp = [False for i in range(m + 1)]
        #init states
        dp[0] = True

        for i in range(1, len(A)+1):
            """
            每个item只能取一次
            从后往前，这样才不会重复计算
            """
            for j in range(m, 0, -1):
                if j - A[i-1] >= 0 and dp[j-A[i-1]]:
                    dp[j] = True

        for i in range(m, -1, -1):
            if dp[i]:
                return i