Signature

The 0-1 Knapsack Problem Investigated

Sep 10, 2016

Introduction

The knapsack problem is another classic problem in Computer Science (specficially Combinatorial Optimization). The problem is such: A person is going camping and has a list of items, each with a weight and a value. The person has set a weight limit of W and wants bring items such to maximize the sum of values. From here, there are several variations:

Variations on the number of times an object is used:

  • 0-1: Each object can be unused or used once.
  • Bounded: Each object can be unused or used up to n times.
  • Unbounded: Each object can be used non-negative times (zero to infinity).

Variations on the values:

  • Values are all equal (Coin Change problem)
  • Values are different

In this post, we will tackle the unbounded knapsack problem using a few different approaches. We will use the list of items, weights, and values from Rosetta Code, an awesome wiki that provides implementations of algorithms across languages.

items = (
    ("map", 9, 150), ("compass", 13, 35), ("water", 153, 200), ("sandwich", 50, 160),
    ("glucose", 15, 60), ("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40),
    ("cheese", 23, 30), ("beer", 52, 10), ("suntan cream", 11, 70), ("camera", 32, 30),
    ("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40),
    ("waterproof trousers", 42, 70), ("waterproof overclothes", 43, 75),
    ("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12),
    ("socks", 4, 50), ("book", 30, 10),
    )
max_weight = 400

Example 2a: 0-1 Knapsack Problem (Recursive)

First we will approach the 0-1 Knapsack Problem using recursion:

def zero_one_knapsack_rec(items, max_weight):
    if not items:
        return ()
    head = items[0]
    tail = items[1:]
    include_head = (head,) + zero_one_knapsack_rec(tail, max_weight-head[1])
    exclude_head = zero_one_knapsack_rec(tail, max_weight)
    if value_of_items(include_head, max_weight) > value_of_items(exclude_head, max_weight):
        return include_head
    else:
        return exclude_head

This solution is fairly simple. When there are no items left, return. Otherwise, get the score (sum of values) of the knapsack with the head of the list included and the score of the knapsack without the head of the list. So, in each recursive call, we determine whether or not the first item will contribute to a more efficient packing than the rest of the items.

This is clearly not very efficient. Adding a global to keep track of the number of calls returns 8388607 (!!!). Consider the recursion tree of this program. Each time the function is called, two recursive calls are made. This happens n times because we are removing at most one element at each level. Thus our program runs at a horrifying O(2^n). For fun, I did some quick arithmetic and found that 8388607 = 2*(2^22), where 22 = number of items (n). We can certainly improve on this with a dynamic programming solution.

Example 2b: 0-1 Knapsack Problem (Dynamic Programming)

To implement a DP solution, simply add a cache. We can do this internally like so:

def zero_one_knapsack_dp(items, max_weight, cache=None):
    global rec_count 
    rec_count += 1
    if not cache:
        cache = {}
    if not items:
        return ()
    head = items[0]
    tail = items[1:]
    if (head, max_weight) in cache:
        include_head = cache[(head, max_weight)]
    else:
        include_head = (head,) + zero_one_knapsack_dp(tail, max_weight-head[1], cache)
        cache[(head, max_weight)] = include_head
    if (tail,max_weight) in cache:
        exclude_head = cache[(tail,max_weight)]
    else:
        exclude_head = zero_one_knapsack_dp(tail, max_weight, cache)
        cache[(tail, max_weight)] = exclude_head
    if value_of_items(include_head, max_weight) > value_of_items(exclude_head, max_weight):
        return include_head
    else:
        return exclude_head

This solution only takes 76633 calls! The runtime is O(n*max_weight) where n = number of items and w = the max weight of the knapsack because the function is called at most for each item and for each unit of weight. If you consider each item weight 1 unit, you can see why we multiply my the maximum weight. This is much faster than before!

References

“If I have seen further it is by standing on the sholders [sic] of Giants.” - Sir Issac Newtown (and many before him)

Knapsack Problem

Knapsack Problem Implementation

Dynamic Programming Approach