Python Solution for Max Value of a Backpack (no partial items)

python_knapsack_01.py

vals = [1,4,5,7] # the subjective values of the items
wts = [1,3,4,5] # the weights of the items
capacity = 7 # the max that the backpack can hold

# set-up the empty table
w, h = capacity+1, len(vals); # adding 1 to capacity since we start at zero
table = [[0 for x in range(w)] for y in range(h)]

# The outer loop is indexing against [0,1,2,3] which index
# into the vals and wts array

for index in range(len(vals)):
    # The inner loop deals with the spectrum of weights, 0 through 7
    # obviously a weight of zero will take no items for each of the rows
    
    for weight in range(1, capacity+1):
        if wts[index] > weight: # if the weight of our item exceeds the column's capacity then take the 
                                # value immediately above it
            table[index][weight] = table[index-1][weight]
            continue

        if wts[index] <= weight:
            # if the item can fit into the weight column slot
            # get the prior best value for comparison with the new option
            # the new option is the sneaky part, it's the value of the item on the row we're dealing with
            # but also adding that current item value to the prior row (up 1) and left by 
            # the column's weight minus the current row's weight
            prior_best = table[index-1][weight]
            new_option_best = vals[index] + table[index-1][weight - wts[index]]
            table[index][weight] = max(prior_best, new_option_best)

        
print(table[-1][-1])
table