卖萌的弱渣

I am stupid, I am hungry.

Backpack

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

Note

You can not divide any item into small pieces.

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.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

Solution

(Backpack.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

# 2d array
    def backPack(self, m, A):
        # write your code here
        l = len(A)
        s = min(max(A),m)
        dp = [[0]*(s+1) for i in range(l+1)]
        for i in range(l):
            for j in range(s+1):
                if A[i] <= j:
                    dp[i+1][j] = max(dp[i][j], dp[i][j-A[i]] + A[i])
                else:
                    dp[i+1][j] = dp[i][j]
        return dp[l][m]
# 1d array
    def backPack(self,m,A):
        # write your code here
        n = len(A)
        dp = [0 for x in range(m+1)]
        dp[0] = 1
        ans = 0
        for item in A:
            for i in range(m,-1,-1):
                if i-item >=0 and dp[i-item] > 0:
                    ans = max(ans,i)
                    dp[i] = 1
        return ans