Skip to content

Instantly share code, notes, and snippets.

@dongr0510
Created September 7, 2020 22:15
Show Gist options
  • Save dongr0510/e4471dafa97df9f1140502ff93bc04a2 to your computer and use it in GitHub Desktop.
Save dongr0510/e4471dafa97df9f1140502ff93bc04a2 to your computer and use it in GitHub Desktop.
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