Solution to the 0-1 knapsack

Question

I'm using a one-dimensional array with length \$W(\text{weight capacity})\$. Is this is any better than the solutions with a two-dimensional array \$W, n\$ where \$n\$ is the number of items? I'm looking for code review, optimizations and best practices.

class Thieves:

    def __init__(self, details, items):
        self.details = details
        self.items = items
        self.index = [None] * (self.details[1] + 1)

    def valuable(self):
        ind = 0

        while ind < len(self.items):

            to_be_added = set()

            for i in range(1, len(self.index)):

                if self.items[ind][0] <= self.details[1]:

                    if self.index[i] == self.items[ind][1] and i == self.items[ind][0]:
                        if self.index[i * 2] != None:
                            if self.index[i * 2] < self.index[i] * 2:
                                self.index[i * 2] = self.index[i] * 2
                        else:
                            self.index[i * 2] = self.index[i] * 2


                    if i == self.items[ind][0]:
                        if self.index[i] != None and self.index[i] < self.items[ind][1]:
                            self.index[i] = self.items[ind][1]

                        elif self.index[i] == None:
                            self.index[i] = self.items[ind][1]


                    if i - self.items[ind][0] > 0 and i - self.items[ind][0] != self.items[ind][0]: #and self.index[self.items[ind][0]] == self.items[ind]  #and self.index[self.items[ind][0]] == self.items[ind][0]:
                        if self.index[i - self.items[ind][0]] != None and self.index[i] == None:
                            value = self.index[i - self.items[ind][0]] + self.items[ind][1]
                            to_be_added.add((i, value))

                        elif self.index[i - self.items[ind][0]] != None and self.index[i] != None:
                            if self.index[i] < self.index[i - self.items[ind][0]] + self.items[ind][1]:
                                to_be_added.add((i,self.index[i - self.items[ind][0]] + self.items[ind][1]))

            #print to_be_added
            for i in to_be_added:
                self.index[i[0]] = i[1]
            to_be_added = set()

            ind += 1

        print self.index[self.details[1]]

def main():

    t = Thieves((5, 5), [[3, 5], [7, 100], [1, 1], [1, 1], [2, 3]])
    t.valuable()

    z = Thieves((12, 5), [[3, 5], [7, 100], [1, 1], [1, 1], [2, 3], [3, 10], [2, 11], [1, 4], [1, 7], [5, 20], [1, 10], [2, 15]])
    z.valuable()

    k = Thieves((4, 10), [[6, 30], [3, 14], [4, 16], [2, 9]])
    k.valuable()

Answer 1

Your code is very hard to follow. Your variable names tell very little about what they are supposed to be, and there are mysterious things, like why details is a 2-tuple, when only the second value in it is used. The very long lines make it hard to follow as well. It is also not obvious to figure out which of the values in every item is the weight and which the value.

So while I am not really sure of what that code is doing, you only need to keep the full 2D array in memory if you want to backtrack over it to find out which items you should take with you. If you are only interested in knowing how much value can fit in the knapsack, you only need to have two rows of the array in memory. And that can be implemented much, much more compactly than what you have come up with:

def knapsack_01(capacity, items):
    # items is sequence of (weight, value) tuples
    prev_row = [0] * (capacity + 1)
    for weight, value in items:
        this_row = prev_row[:weight]
        for idx in range(weight, capacity+1):
            this_row.append(max(prev_row[idx], prev_row[idx-weight] + value))
        prev_row = this_row
    return prev_row[-1]

if __name__ == '__main__':
    items1 = [[3, 5], [7, 100], [1, 1], [1, 1], [2, 3]]
    items2 = [[3, 5], [7, 100], [1, 1], [1, 1], [2, 3], [3, 10], [2, 11],
              [1, 4], [1, 7], [5, 20], [1, 10], [2, 15]]
    items3 = [[6, 30], [3, 14], [4, 16], [2, 9]]
    assert knapsack_01(5, items1) == 8
    assert knapsack_01(5, items2) == 36
    assert knapsack_01(10, items3) == 46

Note that the tests, which all pass, run your test samples against the values returned by your code. So both this and your implementation agree, which is a good thing.

Answer 2

When creating classes in Python 2, you need to have classes explicitly inherit from object, like this:

class MyClass(object):
    ...

If you're creating a class in Python 3, you don't need to explicitly inherit from object.

---

As the classic Stop Writing Classes puts it, one characteristic of a class that should be a function is if the class has only two methods, __init__, and another. This means that your Thieves class would become one method, like this:

def thieves(details, items):
    ...