"""
knapsack.py

You are given ten different items 
with values [505, 352, 458, 220, 354, 414, 498, 545, 473, 543] 
and weights [23, 26, 20, 18, 32, 27, 29, 26, 30, 27].

What is the largest value you can get while keeping the weight under 67? 

 Following https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem,
 define max_value[i, w] = maximum value using items 1,2,3,...,i .
 and set values[0] = weights[0] = 0 to mean "no item", 
 so values[1] is the 1st item, with value 505.

 Then the recursive definition of max_value[i, w] is 

 m[0, w] = 0                                       # no items => no value
 m[i, w] = weight[i] >  w : m[i-1, w]              # doesn't fit => don't use
           weight[i] <= w : max(m[i-1, w] ,        # best choice of use or not
                                m[i-1, w-weight[i]] + value[i])

 This algorithm is called "pseudo-polynomial" because it depends not
 only the number of items i but also on the size of the values involved;
 with values up to 600 as I have here, we (may) need all of the 0...599
 possible smaller values no matter how many items we have. 

 We an N * W matrix of sub-solutions, where W = max(weights) and 
 N = number of items, and we essentially loop over this matrix (or make a
 memoized cache), so this runs in O(N*W).

 Since the book loops over that matrix to build it, I'll do something
 different, namely define a recursive function for one entry in the matrix,
 and memoize it so that we don't calculate anything more than once. 

 And for thi example, I'll do that memoizationg using a tricky python
 syntax called a "decorator class", which lets you apply memoization to 
 any function you like. There are advanced features of python in play here :

   * First, each instance of the memoize class is callable since it
     has a __call__ method.  That means that each instance can be
     treated as a function.

   * Second, the "@decorator" syntax before a function means
     "replace this function with the one returned by creating
     one of these". So the function "knapsack" is replaced
     by an instance of "memoize".

   * And third, since I want to let the function have any 
     number of arguments, I used the f(*x) notation which
     turns all the arguments into a tuple, so if we call 
     f(2,3,4), then within f, x[0] for example would be 2.

 I've also put some diagnostics into the memoization, so that 
 it can display what's going on during the tree of recursive calls.
 
 Tested with python 3.5.6.

    $ python knapsack.py 
    Solving the knapsack problem with 
      weights = [23, 26, 20, 18, 32, 27, 29, 26, 30, 27]
      values = [505, 352, 458, 220, 354, 414, 498, 545, 473, 543]
      target = 67
         eval 1, call 1 : knapsack(10, 67)
         eval 2, call 2 : knapsack(9, 67)
         eval 3, call 3 : knapsack(8, 67)
         eval 4, call 4 : knapsack(7, 67)
         eval 5, call 5 : knapsack(6, 67)
         eval 6, call 6 : knapsack(5, 67)
         eval 7, call 7 : knapsack(4, 67)
         eval 8, call 8 : knapsack(3, 67)
         eval 9, call 9 : knapsack(2, 67)
         eval 10, call 10 : knapsack(1, 67)
         eval 11, call 11 : knapsack(0, 67)
         eval 12, call 12 : knapsack(0, 44)
         eval 13, call 14 : knapsack(1, 41)
         eval 14, call 15 : knapsack(0, 41)
         eval 15, call 16 : knapsack(0, 18)
         eval 16, call 19 : knapsack(2, 47)
         eval 17, call 20 : knapsack(1, 47)
         eval 18, call 21 : knapsack(0, 47)
         eval 19, call 22 : knapsack(0, 24)
         eval 20, call 24 : knapsack(1, 21)
         eval 21, call 25 : knapsack(0, 21)
         eval 22, call 28 : knapsack(3, 49)
         eval 23, call 29 : knapsack(2, 49)
         eval 24, call 30 : knapsack(1, 49)
         eval 25, call 31 : knapsack(0, 49)
         eval 26, call 32 : knapsack(0, 26)
         eval 27, call 34 : knapsack(1, 23)
         eval 28, call 35 : knapsack(0, 23)
         eval 29, call 36 : knapsack(0, 0)
         eval 30, call 39 : knapsack(2, 29)
         eval 31, call 40 : knapsack(1, 29)
         eval 32, call 41 : knapsack(0, 29)
         eval 33, call 42 : knapsack(0, 6)
         eval 34, call 44 : knapsack(1, 3)
         eval 35, call 45 : knapsack(0, 3)
         eval 36, call 49 : knapsack(4, 35)
         eval 37, call 50 : knapsack(3, 35)
         eval 38, call 51 : knapsack(2, 35)
         eval 39, call 52 : knapsack(1, 35)
         eval 40, call 53 : knapsack(0, 35)
         eval 41, call 54 : knapsack(0, 12)
         eval 42, call 56 : knapsack(1, 9)
         eval 43, call 57 : knapsack(0, 9)
         eval 44, call 59 : knapsack(2, 15)
         eval 45, call 60 : knapsack(1, 15)
         eval 46, call 61 : knapsack(0, 15)
         eval 47, call 63 : knapsack(3, 17)
         eval 48, call 64 : knapsack(2, 17)
         eval 49, call 65 : knapsack(1, 17)
         eval 50, call 66 : knapsack(0, 17)
         eval 51, call 69 : knapsack(5, 40)
         eval 52, call 70 : knapsack(4, 40)
         eval 53, call 71 : knapsack(3, 40)
         eval 54, call 72 : knapsack(2, 40)
         eval 55, call 73 : knapsack(1, 40)
         eval 56, call 74 : knapsack(0, 40)
         eval 57, call 77 : knapsack(1, 14)
         eval 58, call 78 : knapsack(0, 14)
         eval 59, call 80 : knapsack(2, 20)
         eval 60, call 81 : knapsack(1, 20)
         eval 61, call 82 : knapsack(0, 20)
         eval 62, call 84 : knapsack(3, 22)
         eval 63, call 85 : knapsack(2, 22)
         eval 64, call 86 : knapsack(1, 22)
         eval 65, call 87 : knapsack(0, 22)
         eval 66, call 88 : knapsack(2, 2)
         eval 67, call 89 : knapsack(1, 2)
         eval 68, call 90 : knapsack(0, 2)
         eval 69, call 93 : knapsack(4, 8)
         eval 70, call 94 : knapsack(3, 8)
         eval 71, call 95 : knapsack(2, 8)
         eval 72, call 96 : knapsack(1, 8)
         eval 73, call 97 : knapsack(0, 8)
         eval 74, call 100 : knapsack(6, 38)
         eval 75, call 101 : knapsack(5, 38)
         eval 76, call 102 : knapsack(4, 38)
         eval 77, call 103 : knapsack(3, 38)
         eval 78, call 104 : knapsack(2, 38)
         eval 79, call 105 : knapsack(1, 38)
         eval 80, call 106 : knapsack(0, 38)
         eval 81, call 109 : knapsack(1, 12)
         eval 82, call 112 : knapsack(2, 18)
         eval 83, call 113 : knapsack(1, 18)
         eval 84, call 116 : knapsack(3, 20)
         eval 85, call 118 : knapsack(2, 0)
         eval 86, call 119 : knapsack(1, 0)
         eval 87, call 123 : knapsack(4, 6)
         eval 88, call 124 : knapsack(3, 6)
         eval 89, call 125 : knapsack(2, 6)
         eval 90, call 126 : knapsack(1, 6)
         eval 91, call 129 : knapsack(5, 11)
         eval 92, call 130 : knapsack(4, 11)
         eval 93, call 131 : knapsack(3, 11)
         eval 94, call 132 : knapsack(2, 11)
         eval 95, call 133 : knapsack(1, 11)
         eval 96, call 134 : knapsack(0, 11)
         eval 97, call 137 : knapsack(7, 41)
         eval 98, call 138 : knapsack(6, 41)
         eval 99, call 139 : knapsack(5, 41)
         eval 100, call 140 : knapsack(4, 41)
         eval 101, call 141 : knapsack(3, 41)
         eval 102, call 142 : knapsack(2, 41)
         eval 103, call 146 : knapsack(2, 21)
         eval 104, call 149 : knapsack(3, 23)
         eval 105, call 150 : knapsack(2, 23)
         eval 106, call 152 : knapsack(2, 3)
         eval 107, call 156 : knapsack(4, 9)
         eval 108, call 157 : knapsack(3, 9)
         eval 109, call 158 : knapsack(2, 9)
         eval 110, call 161 : knapsack(5, 14)
         eval 111, call 162 : knapsack(4, 14)
         eval 112, call 163 : knapsack(3, 14)
         eval 113, call 164 : knapsack(2, 14)
         eval 114, call 167 : knapsack(6, 12)
         eval 115, call 168 : knapsack(5, 12)
         eval 116, call 169 : knapsack(4, 12)
         eval 117, call 170 : knapsack(3, 12)
         eval 118, call 171 : knapsack(2, 12)
         eval 119, call 175 : knapsack(8, 37)
         eval 120, call 176 : knapsack(7, 37)
         eval 121, call 177 : knapsack(6, 37)
         eval 122, call 178 : knapsack(5, 37)
         eval 123, call 179 : knapsack(4, 37)
         eval 124, call 180 : knapsack(3, 37)
         eval 125, call 181 : knapsack(2, 37)
         eval 126, call 182 : knapsack(1, 37)
         eval 127, call 183 : knapsack(0, 37)
         eval 128, call 190 : knapsack(3, 19)
         eval 129, call 191 : knapsack(2, 19)
         eval 130, call 192 : knapsack(1, 19)
         eval 131, call 193 : knapsack(0, 19)
         eval 132, call 195 : knapsack(4, 5)
         eval 133, call 196 : knapsack(3, 5)
         eval 134, call 197 : knapsack(2, 5)
         eval 135, call 198 : knapsack(1, 5)
         eval 136, call 199 : knapsack(0, 5)
         eval 137, call 201 : knapsack(5, 10)
         eval 138, call 202 : knapsack(4, 10)
         eval 139, call 203 : knapsack(3, 10)
         eval 140, call 204 : knapsack(2, 10)
         eval 141, call 205 : knapsack(1, 10)
         eval 142, call 206 : knapsack(0, 10)
         eval 143, call 208 : knapsack(6, 8)
         eval 144, call 209 : knapsack(5, 8)
         eval 145, call 212 : knapsack(7, 11)
         eval 146, call 213 : knapsack(6, 11)
         eval 147, call 217 : knapsack(9, 40)
         eval 148, call 218 : knapsack(8, 40)
         eval 149, call 219 : knapsack(7, 40)
         eval 150, call 220 : knapsack(6, 40)
         eval 151, call 222 : knapsack(5, 13)
         eval 152, call 223 : knapsack(4, 13)
         eval 153, call 224 : knapsack(3, 13)
         eval 154, call 225 : knapsack(2, 13)
         eval 155, call 226 : knapsack(1, 13)
         eval 156, call 227 : knapsack(0, 13)
         eval 157, call 231 : knapsack(7, 14)
         eval 158, call 232 : knapsack(6, 14)
         eval 159, call 235 : knapsack(8, 10)
         eval 160, call 236 : knapsack(7, 10)
         eval 161, call 237 : knapsack(6, 10)
    The answer is 1270.
    The function was called 240 times.

 *Now* we're having fun.

Jim Mahoney | cs.marlboro.college | April 2019 | MIT License

"""

class memoize:
    """ Turn a function into a memoized version of itself,
        namely one that caches each f(*args)=result and
        therefore never calculates the same result from
        the same *args twice. 
        >>> @memoize
        ... def return_it(x):         # ... modified by memoize.
        ...     return(x)
        >>> return_it(3)              # first (3) => evaluate it
             eval 1, call 1 : return_it(3,)
        3
        >>> return_it(4)              # first (4) => evaluate it.
             eval 2, call 2 : return_it(4,)
        4
        >>> return_it(3)              # second (3) => return cached value.
        3
    """
    def __init__(self, function):
        self.function = function
        self.cache = {}
        self.eval_count = 0
        self.call_count = 0
    def __call__(self, *args):
        self.call_count += 1
        key = str(args)      # Make sure that the cache key is immutable.
        if not key in self.cache:
            self.eval_count += 1
            print("     eval {}, call {} : {}{}".format(
                self.eval_count, self.call_count,
                self.function.__name__, str(args)))
            self.cache[key] = self.function(*args)
        return self.cache[key]

# The recommended python style is to capitalize constants;
# see https://www.python.org/dev/peps/pep-0008/
VALUE  = [0, 505, 352, 458, 220, 354, 414, 498, 545, 473, 543]
WEIGHT = [0, 23, 26, 20, 18, 32, 27, 29, 26, 30, 27]
TARGET = 67          # target value
N = len(VALUE) - 1   # item count (VALUE[0] and WEIGHT[0] are "no item")

@memoize
def knapsack(i, w):
    """ Return the best value for the knapsack problem 
        for weight w using items 1..i ... recursively. """
    # Short and sweet. :)
    if i == 0:
        return 0
    else:
        without_i = knapsack(i - 1, w)  # Best solution using items 1 ... i-1.
        if WEIGHT[i] > w:               # Can't ever use item i - to big - 
            return without_i            # so return the solution without it.
        else:
            with_i = knapsack(i - 1, w - WEIGHT[i]) + VALUE[i]
            return max(with_i, without_i)

def main():
    print("Solving the knapsack problem with ")
    print("  weights = {}".format(WEIGHT[1:]))
    print("  values = {}".format(VALUE[1:]))
    print("  target = {}".format(TARGET))
    answer = knapsack(N, TARGET)
    print("The answer is {}.".format(answer))
    print("The function was called {} times.".format(knapsack.call_count))

if __name__ == '__main__':
    import doctest
    doctest.testmod()
    main()