Skip to content

Instantly share code, notes, and snippets.

@dongr0510
Created September 7, 2020 23:08
Show Gist options
  • Save dongr0510/5e81824aa0c65388866edfdaf6109152 to your computer and use it in GitHub Desktop.
Save dongr0510/5e81824aa0c65388866edfdaf6109152 to your computer and use it in GitHub Desktop.
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]
@TheGreatJoules
Copy link

Small syntax error line 21 variable should be profit1 👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment