knapsack.py

#! /usr/bin/env python

import collections
import functools
import random

class Item(collections.namedtuple('_Item', "value weight")):

    @classmethod
    def random(cls):
        """ Return a random Item object. """

        value  = random.randint(1, 100)
        weight = random.randint(1, 25)
        return cls(value, weight)

@functools.lru_cache(maxsize=None)
def knapsack(items, capacity):
    """ A Pythonic solution to the 0/1 knapsack problem.

    Kudos to this answer on Stack Exchange:
    http://codereview.stackexchange.com/a/20581

    """

    if not items or not capacity:
        return 0, []

    item = items[-1]
    rest = items[:-1]

    # If we put this item in the knapsack, we need to solve the problem
    # for the remaining items, subtracting the weight of the item from
    # the capacity of the knapsack. If we do not select the item, also
    # solve for the remaining items, but without subtracting the weight.
    # Return the maximum of both possibilities (select / don't select).

    subproblems = []
    # Two element tuple: (total, items)
    dont_choose = knapsack(rest, capacity)
    subproblems.append(dont_choose)

    if item.weight <= capacity:
        sub_max, sub_items = knapsack(rest, capacity - item.weight)
        choose_it = item.value + sub_max, [item] + sub_items
        subproblems.append(choose_it)

    return max(subproblems)

items = (Item(4, 12), Item(2, 1), Item(6, 4), Item(1, 1), Item(2, 2))
capacity = 15
print(knapsack(items, capacity))

#items = tuple(Item.random() for _ in range(25))
#capacity = sum(i.weight for i in items) // 2
#print(knapsack(items, capacity))