"""
 knapsack.py

 The classic knapsack problem.

 Find the most value that will fit 

"""

n = 4                             # number of items = n
capacity = 8                      # maximum weight  = w
value = [15, 10, 9, 5]
weight = [1, 5, 3, 4]

# approach 1: brute force
# O(2**n) 
# (0,1) version of problem i.e. zero or one of each item.

"Do in class"

#      box 1
#    /in      \out
#    2         2
#   / \        / \
#

def search(total_weight, total_value, i_next, in_or_out):
    """ Search of graph of possible in/out assignments
        Return (value, in_out) best of the two choices """
    if i_next >= n:
        return (total_value, in_or_out)
    inout_copy = list(in_or_out)   # make copy
    new_weight = total_weight + weight[i_next]
    if new_weight > capacity:
        return search(total_weight, total_value,
                      i_next+1, inout_copy)
    else:
        # this one not in bag
        (value1, inout1) = search(total_weight, total_value,
                                  i_next+1, inout_copy)
        # this one in bag
        inout_copy2 = list(inout_copy)  # make copy
        inout_copy2[i_next] = True
        new_value = total_value + value[i_next]
        (value2, inout2) = search(new_weight, new_value,
                                  i_next+1, inout_copy2)
        if value1 > value2:
            return (value1, inout1)
        else:
            return (value2, inout2)

def main():
    in_or_out = [False] * n
    total_weight = 0
    total_value = 0
    i_next = 0
    (value, inout) = search(total_weight, total_value,
                            i_next, in_or_out)
    print "value = %i" % value
    print "inout = %s" % str(inout)

main()

# approach 2: dynamic programming
# O(n*w)
#   answer[i, w] = i items, max value up to capacity=w
#   edge conditions :    answer[0,w] no items = answer[i,0] no weight = 0
#   recursion relation : answer[i,w] = max (v[j] + answer[i-1,w])
#                                      for j not yet in bag & total weight < w

"Do in class"