forked from kamyu104/LintCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbackpack.py
More file actions
36 lines (34 loc) · 1.21 KB
/
backpack.py
File metadata and controls
36 lines (34 loc) · 1.21 KB
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
# Time: O(n*m)
# Space: O(m)
#
# Given n items with size A[i], 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 and 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.
#
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
d = [[False for j in xrange(m+1)] for i in xrange(2)]
result = 0
d[0][0] = True
for i in xrange(1, len(A) + 1):
d[i%2][0] = True
for j in xrange(1, m+1):
d[i%2][j] = d[(i-1)%2][j]
if j >= A[i-1]:
d[i%2][j] = d[(i-1)%2][j] or d[(i-1)%2][j-A[i-1]]
if d[i%2][j]:
result = max(result, j)
return result