Skip to content

Instantly share code, notes, and snippets.

Created September 7, 2020 22:21
  • 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):
# 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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment