dynamic programming code

DynamicAlgo.py

"It's a reworked version of Problem 14 that you find here: http://interactivepython.org/runestone/static/pythonds/Recursion/pythondsProgrammingExercises.html"

dizio_1 = { (2,2): 1, (3,4): 2, (4,6): 3, (5,7): 4, (9,10): 5, (9,11): 6, (13,15): 7, (16,19): 8, \
 (25,37): 9, (35,45):10  }

def createTab ( _Dict ): #create the graphic tab
    dizio = _Dict
    print('','Item', 'Weight', 'Value','\n', sep="       " )
    for key in dizio:
        spazio = "           "
        print("        ", str(dizio[key]).ljust(len(spazio)), str(key[0]).ljust(len(spazio)), str(key[1]))

print()
createTab(dizio_1)
print('\n\n')

def bottomUpDynamic(dizio, weightAvail):
    weightValues = dict(dizio.keys())
    r = [0] * weightAvail # the list where we will put the maximum value for each bearable weight
    s = [0] * weightAvail # the list where the each element represents the weight "taken"
    q = 0
    for j in range(2, weightAvail+1):
        for i in [c for c in weightValues if c <= j]:
            if q < weightValues[i] + r[j-1 - i]:
                q = weightValues[i] + r[j-1 - i]
                s[j-1] = i
        r[j-1] = q
    return r,s

Bearable_weight = 38
r,s = bottomUpDynamic(dizio_1, Bearable_weight)

for g,k in enumerate(r):
    if g+1 == Bearable_weight:
        print('Bearable weight by the knapsack: {} => Maximum profit obtainable : {}'.format(g+1,k))

print('\n/-----/\n')

from itertools import groupby

def printCombination(weightAvail):
    print("Items in the knapsack: \n")
    global s, dizio_1
    dizio = { x[0]: dizio_1[x] for x in dizio_1 }
    new = []
    while weightAvail > 0:
        if s[weightAvail-1] in dizio:  # this condition is necessary because when a weight is in
        # our initial dizio_1 but it is "not taken" it generates 0 as value in s, and so it
        # doesn't exist anymore in dizio and we must take one step back in the iteration.
            new.append(dizio[s[weightAvail-1]])
            weightAvail -= s[weightAvail-1]
        else:
            weightAvail -= 1
    for s,g in groupby(new):
        print("Item {} taken {} times ".format(s, len(list(g))))

printCombination(Bearable_weight)