0/1 Knapsack (medium)

def solve_knapsack(profits, weights, capacity):
  # create a two dimensional array for Memoization, each element is initialized to '-1'
  dp = [[-1 for x in range(capacity+1)] for y in range(len(profits))]
  return knapsack_recursive(dp, profits, weights, capacity, 0)
def knapsack_recursive(dp, profits, weights, capacity, currentIndex):
  # base checks
  if capacity <= 0 or currentIndex >= len(profits):
    return 0
  # if we have already solved a similar problem, return the result from memory
  if dp[currentIndex][capacity] != -1:
    return dp[currentIndex][capacity]
  # recursive call after choosing the element at the currentIndex
  # if the weight of the element at currentIndex exceeds the capacity, we
  # shouldn't process this
  profit1 = 0
  if weights[currentIndex] <= capacity:
    profit1 = profits[currentIndex] + knapsack_recursive(
      dp, profits, weights, capacity - weights[currentIndex], currentIndex + 1)
  # recursive call after excluding the element at the currentIndex
  profit2 = knapsack_recursive(
    dp, profits, weights, capacity, currentIndex + 1)
  dp[currentIndex][capacity] = max(profit1, profit2)
  return dp[currentIndex][capacity]
def main():
  print(solve_knapsack([1, 6, 10, 16], [1, 2, 3, 5], 7))
  print(solve_knapsack([1, 6, 10, 16], [1, 2, 3, 5], 6))
main()

def solve_knapsack(profits, weights, capacity):
  # create a two dimensional array for Memoization, each element is initialized to '-1'
  dp = [[-1 for x in range(capacity+1)] for y in range(len(profits))]
  
  print("Initialized a two dimensional array dp: ")
  print_matrix(dp,0)
  result = knapsack_recursive(dp, profits, weights, capacity, 0)
  return result
 
def print_matrix(dp,current_index):
  print()
  print("\t"*current_index,"     ",end=" ")
  for k in range(len(dp[0])):
    print(k,end="   ")
  print()
 
  print("\t"*current_index,"-"*40)
 
  for i in range(len(dp)):
    print("\t"*current_index,i,end= "  | ")
    for j in range(len(dp[i])):
      if(j == len(dp[i])-1):
        if(dp[i][j]<0 or dp[i][j]>9):
          print(dp[i][j])
        else:
          print ("",dp[i][j])
      else:
        if(dp[i][j]<0 or dp[i][j]>9):
          print(dp[i][j],end="  ")
        else:
          print ("",dp[i][j],end="  ")
  # print("\n")
 
def knapsack_recursive(dp, profits, weights, capacity, current_index):
 
  print("\t"*current_index, "Method knapsack_recursive called with parameters:",end=" ")
  print("current_index: ",current_index,end=" ")
  print("  ","capacity: ",capacity)
  # base checks
  if capacity <= 0 or current_index >= len(profits):
    print("\t"*current_index, "failed base checks")
    return 0
 
 # if we have already solved a similar problem, return the result from memory
  if dp[current_index][capacity] != -1:
    print("\t"*current_index,"We already know the profit:", dp[current_index][capacity])
    return dp[current_index][capacity]
 
 # recursive call after choosing the element at the current_index
 # if the weight of the element at current_index exceeds the capacity, we
 # shouldn't process this
  profit1 = 0
  if weights[current_index] <= capacity:
    print("\t"*current_index, "  Computing profit while including item at index", current_index)
   #print("\t"*current_index,"profits[current_index]: ",profits[current_index])
    profit1 = profits[current_index] + knapsack_recursive(
     dp, profits, weights, capacity - weights[current_index], current_index + 1)
    print("\t"*current_index, "  Profit when capacity is", capacity, "and item at index", current_index, "is included:", profit1)
  else:
    print("\t"*current_index, " Current item is too heavy (weight: ", weights[current_index], ") for the knapsack. Hence the profit is 0.", sep="")
  
  dp[current_index][capacity] = profit1
  print("\t"*current_index,"dp, after updating: ", end="")
  print_matrix(dp, current_index)
  return dp[current_index][capacity]
 
 
def main():
  knapsacks = [[[1, 2, 5, 7], [1, 2, 3, 4], 5],[[1,2,3],[1,2,3],4], [[1, 6, 10, 16], [1, 2, 3, 5], 7]]
 
  for knapsack in knapsacks:
    print("Solving for the following parameters: \nProfits: ",knapsack[0]," Weights: ",knapsack[1]," Capacity: ",knapsack[2])
    result = solve_knapsack(knapsack[0], knapsack[1], knapsack[2])
    print("\nMaximum profit: ",result)
    print("-"*100+"\n")
 
main()

def solve_knapsack(profits, weights, capacity):
  # create a two dimensional array for Memoization, each element is initialized to '-1'
  dp = [[-1 for x in range(capacity+1)] for y in range(len(profits))]
 
  print("Initialized a two dimensional array dp: ")
  print_matrix(dp,0)
  result = knapsack_recursive(dp, profits, weights, capacity, 0)
  return result
 
def print_matrix(dp,current_index):
  print()
  print("\t"*current_index,"     ",end=" ")
  for k in range(len(dp[0])):
    print(k,end="   ")
  print()
 
  print("\t"*current_index,"-"*40)
  for i in range(len(dp)):
    print("\t"*current_index,i,end= "  | ")
    for j in range(len(dp[i])):
      if(j == len(dp[i])-1):
        if(dp[i][j]<0 or dp[i][j]>9):
          print(dp[i][j])
        else:
          print ("",dp[i][j])
      else:
        if(dp[i][j]<0 or dp[i][j]>9):
          print(dp[i][j],end="  ")
        else:
          print ("",dp[i][j],end="  ")
  # print("\n")
 
def knapsack_recursive(dp, profits, weights, capacity, current_index):
 
  print("\t"*current_index,"Method knapsack_recursive called with parameters:",end=" ")
  print("current_index: ",current_index,end=" ")
  print("  ","capacity: ",capacity)
  # base checks
  if capacity <= 0 or current_index >= len(profits):
    print("\t"*current_index, "failed base checks")
    return 0
 
 # if we have already solved a similar problem, return the result from memory
  if dp[current_index][capacity] != -1:
    print("\t"*current_index,"We already know the profit:", dp[current_index][capacity])
    return dp[current_index][capacity]
 
 # recursive call after choosing the element at the current_index
 # if the weight of the element at current_index exceeds the capacity, we
 # shouldn't process this
  profit1 = 0
  if weights[current_index] <= capacity:
    print("\t"*current_index, "  Computing profit while including item at index", current_index)
    #print("\t"*current_index,"profits[current_index]: ",profits[current_index])
    profit1 = profits[current_index] + knapsack_recursive(
     dp, profits, weights, capacity - weights[current_index], current_index + 1)
    print("\t"*current_index, "  Profit when capacity is", capacity, "and item at index", current_index, "is included:", profit1)
  else:
    print("\t"*current_index, " Current item is too heavy (weight: ", weights[current_index], ") for the knapsack. Hence the profit from it is 0.", sep="")
  
 
 # recursive call after excluding the element at the current_index
  print("\t"*current_index,"  Computing profit while excluding item at index", current_index)
  profit2 = knapsack_recursive(
   dp, profits, weights, capacity, current_index + 1)
  print("\t"*current_index, "  Profit when capacity is", capacity, "and item at index", current_index, "is excluded:", profit2)
  in_ex = ""
  if profit1 > profit2:
    in_ex = "in"
  else:
    in_ex = "ex"
  print("\t"*current_index, " With capacity at ", capacity, ", we make more profit by ", in_ex, "cluding the item at index ", current_index, sep="")
  dp[current_index][capacity] = max(profit1, profit2)
  print("\t"*current_index,"dp, after updating: ")
  print_matrix(dp, current_index)
  return dp[current_index][capacity]
 
 
def main():
  knapsacks = [[[1, 2, 5, 7], [1, 2, 3, 4], 5],[[1,2,3],[1,2,3],4], [[1, 6, 10, 16], [1, 2, 3, 5], 7]]
 
  for knapsack in knapsacks:
    print("Solving for the following parameters: \nProfits: ",knapsack[0]," Weights: ",knapsack[1]," Capacity: ",knapsack[2])
    result = solve_knapsack(knapsack[0], knapsack[1], knapsack[2])
    print("\nMaximum profit: ",result)
    print("-"*100+"\n")
 
main()