from printtables import printTable, initMat

# inefficient recursive version
def zeroOneKnapsackRec(v, w, W, n=None):
    ''' v = list of item values or profit
        w = list of item weight or cost
        W = max weight for the knapsack
        n = number of items to consider, replaced with len(v) if None
    Return best cost of all items in knapsack taken from first n items.
    '''
    if n is None:
        n = len(v)
    if n == 0 or W == 0:
        return 0
    if (w[n-1] > W): # nth item has index n-1
        return zeroOneKnapsackRec(v, w, W, n-1)
    return max(zeroOneKnapsackRec(v, w, W, n-1),
               v[n-1] + zeroOneKnapsackRec(v, w, W-w[n-1], n-1))

# dynamic, topologically ordered
def zeroOneKnapsack(v, w, W):
    ''' v = list of item values or profit
        w = list of item weight or cost
        W = max weight or max cost for the knapsack
    Return best cost of all items in knapsack, and cost matrix.
    '''
    n = len(v)
    c = initMat(0, n+1, W+1) # 2D list of 0's,  c[0..n][0..W]
    # c[i][j] is max cost of some of items 0..i-1 with total weight <= j
    # c[0][j], c[i][0] correctly start at 0.
    for i in range(n): # consider adding item i, setting c[i+1]
        for j in range(1,W+1):  # max weight j     
            if (w[i] > j):
                c[i+1][j] = c[i][j]
            else:
                c[i+1][j] = max(c[i][j],v[i] +c[i][j-w[i]])

    # for HW print sequence of (value, weight) actually taken,
    #  in increasing order of index.  An extra table not needed.
    
    return (c[n][W], c)

##### display methods
def displayAll(v, w, W):
    best, c = zeroOneKnapsack(v, w, W)
    printTable(c,'\nBest total value {} with max weight {}'.format(best, W),
               'choices', 'max weight',
               colsRight = [('val', ['']+v), ('wt', ['']+w)])
    
displayAll([12, 10, 20, 15], [2, 1, 3, 2], 5)