unbound_bf.py

def solve_knapsack(profits, weights, capacity):
  return solve_knapsack_recursive(profits, weights, capacity, 0)


def solve_knapsack_recursive(profits, weights, capacity, currentIndex):
  n = len(profits)
  # base checks
  if capacity <= 0 or n == 0 or len(weights) != n or currentIndex >= n:
    return 0

  # recursive call after choosing the items at the currentIndex, note that we recursive call on all
  # items as we did not increment currentIndex
  profit1 = 0
  if weights[currentIndex] <= capacity:
    profit1 = profits[currentIndex] + solve_knapsack_recursive(
      profits, weights, capacity - weights[currentIndex], currentIndex)

  # recursive call after excluding the element at the currentIndex
  profit2 = solve_knapsack_recursive(
    profits, weights, capacity, currentIndex + 1)

  return max(profit1, profit2)