Created
September 7, 2020 22:21
-
-
Save dongr0510/fd163ed5e80ae61dba998868ea262328 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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