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

Is this Python3? For this question it makes a difference. range vs xrange. — Peilonrayz
– Peilonrayz ♦, Commented Nov 23, 2015 at 19:10
no, it should be the same, for which the xrange is a generator, that saves memory. — Cheng Gu
– Cheng Gu, Commented Nov 23, 2015 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
– Peilonrayz ♦, Commented Nov 23, 2015 at 19:15

Caridorc · Accepted Answer · 2015-11-23 19:23:58Z

4

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

edited Nov 23, 2015 at 19:23

answered Nov 23, 2015 at 19:11

Caridorc

28.1k7 gold badges55 silver badges138 bronze badges

Add a comment |

Barry · Accepted Answer · 2015-11-23 19:25:04Z

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]

Stack Exchange Network

Improving the time complexity of my back pack algorithm

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Improving the time complexity of my back pack algorithm

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions