The 0/1 Knapsack Problem

The General Problem

The general knapsack problem is a problem in combinatorial optimization. The premise goes like this: given a set of items where each item has an associated weight and value, and a knapsack that can hold a given amount of weight, how do we find the highest value from items while still fitting in the knapsack? Put another way:

We seek the maximize the objective of finding a total value from a combination 
of items subject to the constraint that the items must fit in the knapsack.

There is a reason why I wrote that description in that way. It will become clear why later on in the chapter.

Specializing to the 0/1 Case

Now that we formulated the general knapsack problem, let us place an additional constraint: there is only a single copy of any given item available. This is known as the 0/1 variation of the knapsack problem, the reason being that we may choose to include either 0 or 1 of a given item.

Let's look at a couple of examples to put this into more concrete terms. Suppose we had a set of items where the values are

values = [1, 6, 10, 16]

and the weights are

weights = [1, 2, 3, 5]

If we have a knapsack with capacity of 7 then the maximum value is 22. This is a simple example because the input size is small, so it is easy to enumerate combinations and figure out the answer by inspection.

So how do we proceed to solve it? The brute force way is straightforward so let's go with that: we enumerate all the combinations of items, sum up their values and weights, and pick out the max value that fits in the capacity. Python provides convenience functions for this kind of task in itertools, see here.

The first one is itertools.combinations(iterable, r), where r is an integer. It will return an iterable that yields tuples that are combinations of r items from the input iterable. Let's try it out in the Python console

>>> import itertools as it
>>> s = list(range(5))
>>> s
[0, 1, 2, 3, 4]
>>> list(it.combinations(s, 4))
[(0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 3, 4), (0, 2, 3, 4), (1, 2, 3, 4)]

We need to generate the combinations for all r. There is a convenient function called chain with an alternate constructor called chain.from_iterable which will allow us to chain all the generated iterables into a single iterable.

>>> list(it.chain.from_iterable(combinations(s, r) for r in range(len(s) + 1)))
[(), (0,), (1,), (2,), (3,), (4,), (0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), ...

Now that we have these figured out, let's write out the solution:

def knapsack_01_brute_combinatorial(values, weights, weight):
    from itertools import chain, combinations
    from functools import reduce
    s = zip(values, weights)
    combos = chain.from_iterable(combinations(s, r) for r in range(1, len(s) + 1))
    result = filter(lambda x: x[1] <= weight,
                    map(lambda z: reduce(lambda a, y: (a[0] + y[0], a[1] + y[1]),
                                         z), combos))

    result = max(result, key=lambda x: x[0])[0]
    return result

Functional programmers will be right at home with this kind of code. For those that aren't, let's go over it and make it comprehensible. First, we zip values and weights together, so s is an iterable whose items are tuples of integers of length two, ie (int, int). Now, combos is an iterable whose items are tuples of varying length, and the items of those tuples are the same as in s. Note the range for r is 1..len(s) + 1. We do not need the empty tuple from r=0, but we need the combination from r=len(s), so we need len(s) + 1 in range(). Now we arrive at map, filter, and reduce, the holy trinity (of sorts) of functional programming. They all have a trait in common, in that they all accept a function and an iterable as input and apply that function to each element of the iterable. Let's go over what they do:

• map(func, iterable): returns an iterable and maps each element x of iterable such that each element is func(x). Easily re-written with a list comprehension [func(x) for x in iterable]
• filter(func, iterable): returns an iterable with elements x of iterable such that func(x) returns True. Similar to [x for x in iterable if func(x)]
• reduce(func, iterable, initializer=None): here, func needs to accept two arguments. The first is the accumulator value, it can optionally be given an initial value with initializer. The second argument is an element of iterable. The output of func will be used as the value for the accumulator variable for the next element of iterable. The output of reduce is the final value of the accumulator variable.

It looks a little difficult to follow, but we can make sense by looking where combos is passed in. It is being passed in as an argument to the map. Let's look at that line

map(lambda z: reduce(lambda a, y: (a[0] + y[0], a[1] + y[1]), z), combos)

Recall that the elements of combos are tuples of tuples. The inner tuples represent combinations of items, so we need to sum up the values and weights respectively. That's what the reduce call is for.

reduce(lambda a, y: (a[0] + y[0], a[1] + y[1]), z)

where z is an element of combos. This reduce will gives a tuple of type (int, int). So the result of the lambda in the map will by one of those tuples. Then, the result of the map will be an iterable whose elements are the sums of the values and weights for each combination of items. We therefore just need to discard the elements whose weight exceeds the capacity. That is what filter does for us. We then find the tuple with the highest value and that is our solution. Note, max returns the element, which is a tuple, and we only care about the value which is at the 0 index.

TODO: maybe add a python unittest test case

Discussion

In this section, we looked at the knapsack problem as an example to set the stage for other dynamic programming problems. We solved the 0/1 variation with a brute force naive approach. In the next section we will take a closer look at the 0/1 knapsack variant and see how we can try and optimize our solution.