Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# dongr0510/top_down_knapsack.py

Created Sep 7, 2020
 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]
to join this conversation on GitHub. Already have an account? Sign in to comment