Solves the 0-1 Knapsack problem through dynamic programming

0-1Knapsack.py

###################################################################################
#0-1 Knapsack Problem
# • Find which gems maximize profit given list of values, weights, and weight limit
#
###################################################################################

#Finds the max profit possible with given gems & weight limit
def knapsack(v, w, limit):
    matrix = [[0 for i in range(0, limit+1)] for j in range(0, len(v)+1)]
    
    for i in range(1, len(v)+1):        #Go through rows
        for j in range(1, limit+1):     #Go through columns
            if j >= w[i-1]:             #When gem's weight is at most current weight
                matrix[i][j] = max(matrix[i-1][j], v[i-1] + matrix[i-1][j-w[i-1]])
            else:                       #When gem is heavier than current weight
                matrix[i][j] = matrix[i-1][j]
    
    return matrix

#Finds the gems that achieved the max profit
def findItems(matrix, v, w, limit):
    current = matrix[len(v)][limit] #Current solution
    solution = []

    while current > 0:      #Keeps looping until total value is reached
        temp_list = []
        for i in m:                 #Go through each row to find max value
            temp_list.append(max(i))

        #Finds the lowest index of the current value needed then adds it to bag and updates needed value
        current_index = temp_list.index(current)    
        solution.append(gems[current_index-1])
        current = current - gems[current_index-1]
        
    return solution
        
#Prints matrix in readable format       
def printMat(matrix):
    for i in matrix:
        print(i)


gems = [20, 5, 10, 40, 15, 25]
weights = [1, 2, 3, 8, 7, 4]
limit = 10

m = knapsack(gems, weights, limit)            #Find max value of solution
solution = findItems(m, gems, weights, limit) #Find gems in solution
solution_w = []                               #To store weights of gems in solution
total = 0

#Finds weights of gems in solution
for i in solution:
    w = weights[gems.index(i)]
    solution_w.append(w)
    total = total + w

print("For gems ", gems, "the best value with weight limit ", limit)
print("Are gems ", solution, " for a total of ", m[len(gems)][limit])
print("with weights ", solution_w, " with a total weight of ", total)