Improving the time complexity of my back pack algorithm

Question

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

• Peilonrayz: Is this Python3? For this question it makes a difference. range vs xrange.
• Cheng Gu: no, it should be the same, for which the xrange is a generator, that saves memory.
• Peilonrayz: 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.

Answer 1

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(...):

Answer 2

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]