a solution to an 0-1 knapsack problem

knapsack.py

''' IMPORTANT !!!!
explanation provided entirely by
https://medium.com/@fabianterh/how-to-solve-the-knapsack-problem-with-dynamic-programming-eb88c706d3cf
@fabianterh

i just implemented this in python for bettering my understanding.
'''

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight

    def __repr__(self):
        return F"[{self.weight}, {self.value}]"

class Knapsack:
    def __init__(self, weight_capacity):
        self.weight_capacity = weight_capacity

    def solve(self, items):
        """
        First, we create a 2-dimensional array (i.e. a table) 
        of n + 1 rows and w + 1 columns.
        """

        width = self.weight_capacity
        height = len(items)

        table = [[0 for x in range(width)] for y in range(height)]

        """
        A row number i represents the set of all the items from rows 1— i. 
        For instance, the values in row 3 assumes that we only have items 1, 2, and 3.
        A column number j represents the weight capacity of our knapsack. 
        Therefore, the values in column 5
        
        We can immediately begin filling some entries in our table: 
        the base cases, for which the solution is trivial. 
        For instance, at row 0, when we have no items to pick from, 
        the maximum value that can be stored in any knapsack must be 0
        """

        # technically already zeroed but whatever

        for item, _ in enumerate(table[0]):
            table[0][item] = 0

        for item, _ in enumerate(table):
            table[item][0] = 0

        """
        Now, we want to begin populating our table. 
        As with all dynamic programming solutions at 
        each step, we will make use of our solutions 
        to previous sub-problems.
        """

        """
        The relationship between the value at row i, column j 
        and the values to the previous sub-problems is as follows:
        
        Recall that at row i and column j, we are tackling a sub-problem 
        consisting of items 1, 2, 3 … i with a knapsack of j capacity. 
        There are 2 options at this point: we can either include item i or not. 
        Therefore, we need to compare the maximum value 
        that we can obtain with and without item i.

        The maximum value that we can obtain without item i can be found at 
        row i-1, column j. This part’s easy. The reasoning is straightforward: 
        whatever maximum value we can obtain with items 1, 2, 3 … i must obviously 
        be the same maximum value we can obtain with items 1, 2, 3 … i - 1, 
        if we choose not to include item i.

        To calculate the maximum value that we can obtain with item i, 
        we first need to compare the weight of item i with the knapsack’s weight capacity. 
        Obviously, if item i weighs more than what the knapsack can hold, we can’t include it, 
        so it does not make sense to perform the calculation. In that case, the solution to 
        this problem is simply the maximum value that we can obtain without item i 
        (i.e. the value in the row above, at the same column).

        However, suppose that item i weighs less than the knapsack’s capacity. 
        We thus have the option to include it, if it potentially increases 
        the maximum obtainable value. The maximum obtainable value by including 
        item i is thus = the value of item i itself + the maximum value that 
        can be obtained with the remaining capacity of the knapsack. 
        
        We obviously want to make full use of the capacity of our knapsack, 
        and not let any remaining capacity go to waste.
        """

        for item in range(1, height):
            for capacity in range(1, width):
                max_without = table[item - 1][capacity]
                max_with = 0

                weight_of_current = items[item - 1].weight

                if (capacity >= weight_of_current):
                    max_with = items[item - 1].value

                    remaining_capacity = capacity - weight_of_current
                    max_with += table[item - 1][remaining_capacity]

                table[item][capacity] = max(max_without, max_with)

        return table[height - 1][width - 1]

    def print_table(self, table):
        for row in table:
            print(row)
        print("")

knapsack = Knapsack(10)
items = [Item(10, 5), Item(40, 4), Item(30, 6), Item(50, 3)]
max_value = knapsack.solve(items)
print(max_value)