# Improving the time complexity of my back pack algorithm

Is there anyone who can help me improve the time complexity of this backpack algorithm, for which I already use sliding array to improve the space complexity.

The problem is as follows:

Given n items with size A[i], 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], and the backpack size is 11, we can select [2, 3, 5], so that the max size for this backpack is 10. If the backpack size is 12, we can select [2, 3, 7] and fill it completely.

The 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
n = len(A)
f = [[False for x in range(m+1)] for y in range(2)]
for i in range(n+1):
f[i%2][0] = True

for i in range(1, n+1):
for j in range(1, m+1):
f[i%2][j] = f[(i-1)%2][j]
if j >= A[i-1] and f[(i-1)%2][j-A[i-1]]:
f[i%2][j] = True

max = 0
for i in range(m+1):
if f[n%2][i]:
max = i

return max

• Is this Python3? For this question it makes a difference. range vs xrange. – Peilonrayz Nov 23 '15 at 19:10
• no, it should be the same, for which the xrange is a generator, that saves memory. – Cheng Gu Nov 23 '15 at 19:11
• complexity "Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input." range vs xrange is about space concern. – Peilonrayz Nov 23 '15 at 19:15
• I see, sorry I missed the point, thanks a lot! – Cheng Gu Nov 23 '15 at 19:18

OO is not always appropriate

In this case the class is not needed, just write a free standing function for simplicity.

Make the code speak, not the comments

For example:

# @param m: An integer m denotes the size of a backpack


Can be omitted if you write:

def backPack(backpack_size: int, ...):


and:

# @return: The maximum size


Can be omitted if you write:

def backpack_max_size(...):


I don't know about time complexity, but we can do a lot with readability. There's no reason for your function to be a class method, so let's pull that out. Then, let's rename all our variables be representative of what they are:

def max_backpack_fill(size, weights):
...


Then, we can simplify the construction of your table from:

f = [[False for x in range(m+1)] for y in range(2)]
for i in range(n+1):
f[i%2][0] = True


to:

tbl = [[not x for x in range(size+1)] for y in range(2)]


Rather than using % at every opportunity, it would help to just define the current and previous index up front and use that throughout. Also enumerate comes in handy:

for i, weight in enumerate(weights, start=1):
cur = tbl[i%2]
prev = tbl[(i-1)%2]

for j in xrange(1, size+1):
cur[j] = (j >= weight and prev[j - weight]) or prev[j]


If this is Python2.7, prefer xrange to range throughout.

Lastly, max() takes a key argument, so we can use that here too:

return max(range(size+1), key=lambda i: i if cur[i] else 0)


Altogether:

def max_backpack_fill(size, weights):
tbl = [[not x for x in xrange(size+1)] for y in xrange(2)]

for i, weight in enumerate(weights, start=1):
cur = tbl[i%2]
prev = tbl[(i-1)%2]

for j in xrange(1, size+1):
cur[j] = (j >= weight and prev[j - weight]) or prev[j]

return max(xrange(size+1), key=lambda i: i if cur[i] else 0)


I find this much easier to read.

For more gratuitousness, we could even drop the mod operator, and take advantage of some itertools recipes with:

for weight, (cur, prev) in izip(weights, pairwise(cycle(tbl))):
for j in xrange(1, size+1):
cur[j] = (j >= weight and prev[j-weight]) or prev[j]