Algorithm-LeetCode/Solutions/0092.Backpack.py at main · ling67/Algorithm-LeetCode · GitHub

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
"""
Description
Given n items with size A_{i}A
i

  an integer m denotes the size of a backpack. How full you can fill this backpack?
(Each item can only be selected once and the size of the item is a positive integer)

Contact me on wechat to get Amazon、Google requent Interview questions . (wechat id : jiuzhang15)


You can not divide any item into small pieces.
n \lt 1000n<1000
m \lt 1e9m<1e9
Example
Example 1:

Input:

array = [3,4,8,5]
backpack size = 10
Output:

9
Explanation:

Load 4 and 5.

Example 2:

Input:

array = [2,3,5,7]
backpack size = 12
Output:

12
Explanation:

Load 5 and 7.
"""

from typing import (
    List,
)

"""
dp[i][j] represent first i array number can compose j backpack
dp[n][m]
dp[i][0] = true
dp[0][j] = False
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
"""
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 back_pack(self, size: int, nums: List[int]) -> int:
        # write your code here
        lens = len(nums)

        dp = [[False] * (size+1) for _ in range(lens+1)]
        for i in range(lens+1):
            dp[i][0] = True

        for i in range(1, lens+1):
            for j in range(1, size+1):
                dp[i][j] = dp[i-1][j]

                if j >= nums[i-1]:
                    dp[i][j] = dp[i][j] or dp[i-1][j-nums[i-1]]

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


#滚动数组优化
from typing import (
    List,
)

"""
dp[i][j] represent first i array number can compose j backpack
dp[n][m]
dp[i][0] = true
dp[0][j] = False
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
"""
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 back_pack(self, size: int, nums: List[int]) -> int:
        # write your code here
        n = len(nums)
        dp = [[False] * (size + 1) for _ in range(2)]
        for i in range(2):
            dp[i][0] = True

        for i in range(1, n + 1):
            for j in range(1, size + 1):
                dp[i % 2][j] = dp[(i - 1) % 2][j]
                if j >= nums[i - 1]:
                    dp[i % 2][j] = dp[i % 2][j] or dp[(i - 1) % 2][j - nums[i - 1]]

        for i in range(size, -1, -1):
            if dp[n % 2][i]:
                return i