Knapsack algorithm

knapsack.py

import math
from random import random
import collections
import functools
import logging
import sys

try:
    level = sys.argv[1]
    loglevel = getattr(logging,level)
except IndexError, AttributeError:
    loglevel = logging.DEBUG

logging.basicConfig(level=loglevel)

class memoized(object):
    """Memoization, cache output for nested function
    by arguments"""
    def __init__(self, func):
        self.func = func
        logging.info('Applied memoization to %s',func.__name__)
        self.cache = {}
    def __call__(self, *args):
        if not isinstance(args, collections.Hashable):
            # uncacheable. a list, for instance.
            # better to not cache than blow up.
            return self.func(*args)
        if args in self.cache:
            #logging.info('Values %s found in memoized cache' % args)
            return self.cache[args]
        else:
            value = self.func(*args)
            #logging.info('Caching args %s' % args)
            self.cache[args] = value
            return value
    def __repr__(self):
        '''Return the function's docstring.'''
        return self.func.__doc__
    def __get__(self, obj, objtype):
        '''Support instance methods.'''
        return functools.partial(self.__call__, obj)


def knapsack(items, maxweight):
    """
    Solve the knapsack problem by finding the most valuable
    subsequence of `items` subject that weighs no more than
    `maxweight`.
    """
    
    @memoized
    def bestvalue(i, j):
        if i == 0: return 0
        logging.info('i:%s, j:%s' % (i,j))
        value, weight = items[i - 1]
        if weight > j:
            logging.info('Weight is greater than j:%s, %s' % (j,weight))
            return bestvalue(i - 1, j)
        else:
            retval = max(bestvalue(i - 1, j),bestvalue(i - 1, j - weight) + value)
            logging.info('weight < j:%s, solve for %s' % (j, retval))
            return retval

    j = maxweight
    result = []
    for i in xrange(len(items), 0, -1):
        if bestvalue(i, j) != bestvalue(i - 1, j):
            logging.info('Result found %s, %s' % items[i-1])
            result.append(items[i - 1])
            j -= items[i - 1][1]
    result.reverse()
    return bestvalue(len(items), maxweight), result


if __name__ == '__main__':
    items = []
    for i in xrange(3):
        (value,weight) = math.ceil(random()*100),math.ceil(random()*10)
        items.append((value,weight))
    logging.info('%s items, %s capacity' % (len(items), 8))
    print knapsack(items,8)