Solution to the 0-1 knapsack 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 &lt; len(self.items):

            to_be_added = set()

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

                if self.items[ind][0] &lt;= 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] &lt; 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] &lt; 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] &gt; 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] &lt; 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()
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):
    ...