Python program to implement Knapsack using Dynamic Programming Approach (Binary)

# Knapsack using Dynamic Programming Approach (Binary)

V=[]        # 1D array
W=[]        # 1D array
Table=[]    # 2D array
Keep=[]     # 2D array

kCapacity=0
n=0             # No. of items

def getData():
    global V
    global W
    global Table
    global Keep
    global kCapacity
    global n
    
    kCapacity=int(input("\nEnter Knapsack Capacity: "))
    n=int(input("Enter number of items: "))
    
    for i in range(n):  
        print("\nEnter weight of item ",i+1,": ",end="")
        W.append(0)
        W[i]=int(input())

        print("Enter value of item ",i+1,": ",end="")
        V.append(0)
        V[i]=int(input())

    for i in range(n + 1):  
        Table.append([])
        Keep.append([])         
        for j in range(kCapacity + 1):  
            Table[i].append([])
            Keep[i].append([])
            
            Table[i][j]=0
            Keep[i][j]=0
        

def showInput():
    global V
    global W
    global Table
    global Keep
    global kCapacity
    global n
    
    print("\n*** INPUTS ***\n")

    print("\nKnapsack capacity: ",kCapacity,"\n")
    print("\nItem\tWeight\tValue")
    print("\n-----\t------\t------")
    for i in range(n):
        print("\n",i+1,"\t",W[i],"\t",V[i])


def showOutput():
    global V
    global W
    global Table
    global Keep
    global kCapacity
    global n
    
    print("\n\n")
    print("*** OUTPUTS ***\n\n")

    print("\t\tProfit Calculation Matrix\n")
    print("\t\t-------------------------\n\n")

    for j in range(0, kCapacity+1): 
        print("\t",j,end="")
    print("\n\n")

    for i in range(0,n+1):  
        print(i,end="")
        for j in range(0, kCapacity+1):
            print("\t",Table[i][j],end="")
        print()
    
    # Displaying Keep matrix
    print("\n\t\tKeep Matrix\n")
    print("\t\t-----------\n")
    print()

    for j in range(kCapacity+1):    
        print("\t",j,end="")
    print("\n\n")
    for i in range(n+1):    
        print(i,end="")
        for j in range(kCapacity+1):    
            print("\t",Keep[i][j],end="")
        print()

    print("\n\nSelected items are: ",end="")
    j =kCapacity
    for i in range(n, 0, -1):   
        if Keep[i][j] == 1:
            print("\t",i,end="")
            j=j-W[i-1]
    print("\n\n")


def maximum(x, y):
    if x > y:
        return x
    else:
        return y


# __________________________ Binary Knapsack __________________________
def dynamicKnapsack():
    global V
    global W
    global Table
    global Keep
    global kCapacity
    global n
    
    for i in range(1, n+1): #(int i=1i<n+1i++)
        for j in range(kCapacity+1):    #(int j=1j<kCapacity+1j++)
            if j<W[i-1]:
                Table[i][j]=Table[i-1][j]
            else:
                Table[i][j]=maximum(Table[i-1][j], V[i-1] + Table[i-1][j-W[i-1]] )
                if Table[i-1][j] != Table[i][j]:
                    Keep[i][j]=1
            

# __________________________ Main Block Starts __________________________
print("\t\t\t____Binary Knapsack using Dynamic Programming____")
getData()
showInput()
dynamicKnapsack()
showOutput()

Output