'''knapsack.py

   Jeff Ondich, 18 Feb 2009

   This program solves the knapsack problem as articulated in
   section 6.4 of "Algorithm Design" by Kleinberg & Tardos,
   Pearson Education 2006.  This implementation uses the
   recursion shown in the book without storing intermediate
   answers (i.e. without dynamic programming).
'''

import sys

def fillKnapsack(itemList, n, W, tab=''):
    '''Returns an pair:
    
        (totalValue, optimalItems)

    where totalValue is the optimal total value and optimalItems
    is a list containing a subset of itemList that yields
    the optimal totalValue.
    
    The "tab" parameter helps draw a human-readable trace of
    the recursion.
    '''
    print '%sEntering: %d, %d' % (tab, n, W)
    tab += (3*' ')
    if n == 0:
        (totalValue, optimalItems) = (0, [])
    else:
        (totalValue, optimalItems) = fillKnapsack(itemList, n - 1, W, tab)
        (lastItemValue, lastItemWeight) = itemList[n - 1]
        if W >= lastItemWeight:
            (total, items) = fillKnapsack(itemList, n - 1, W - lastItemWeight, tab)
            total += lastItemValue
            items.append(itemList[n - 1])
            if total > totalValue:
                (totalValue, optimalItems) = (total, items)

    tab = tab[:-3]
    print '%sLeaving: %d, %d' % (tab, n, W), totalValue, optimalItems
    return (totalValue, optimalItems)


items = [(4,5), (7,3), (3,2), (5,2), (4,1)]
capacity = 7
print 'Capacity:', capacity
print 'Items:', items
print fillKnapsack(items, len(items), capacity)