Skip to content

Instantly share code, notes, and snippets.

Created September 7, 2020 22:15
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
def solve_knapsack(profits, weights, capacity):
return knapsack_recursive(profits, weights, capacity, 0)
def knapsack_recursive(profits, weights, capacity, currentIndex):
# base checks
if capacity <= 0 or currentIndex >= len(profits):
return 0
# 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(profits, weights, capacity - weights[currentIndex], currentIndex + 1)
# recursive call after excluding the element at the currentIndex
profit2 = knapsack_recursive(profits, weights, capacity, currentIndex + 1)
return max(profit1, profit2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment