Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
def solve_knapsack(profits, weights, capacity):
n = len(profits)
if capacity <= 0 or n == 0 or len(weights) != n:
return 0
dp = [[0 for x in range(capacity+1)] for y in range(n)]
# populate the capacity = 0 columns, with '0' capacity we have '0' profit
for i in range(0, n):
dp[i][0] = 0
# if we have only one weight, we will take it if it is not more than the capacity
for c in range(0, capacity+1):
if weights[0] <= c:
dp[0][c] = profits[0]
for i in range(1, n):
for c in range(1, capacity+1):
profit1, profit2 = 0, 0
if weights[i] <= c:
profits1 = profits[i] + dp[i-1][c-weights[i]]
profits2 = dp[i-1][c]
dp[i][c] = max(profit1, profit2)
# maximum profit will be at the bottom-right corner.
return dp[n-1][capacity]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment