Problem Link: https://binarysearch.com/problems/0-1-Knapsack
Hello! Today, we’ll be looking at one of the most popular dynamic programming questions: 0–1 Knapsack.
This question can brush up on your fundamental dynamic programming skills as it clearly shows how dynamic programming works so make sure you fully understand this question! Assuming you have fully read and tried this problem, I will go straight to the point.
We have two arrays as input: weights and values. Also, we have the capacity of a “knapsack” into which we want to put items to maximize the total value(profit) of the items in the knapsack.
We can come across TWO important intuitions
- If the current item’s weight is greater than the remaining size of the knapsack, we cannot put that item
- As long as we meet condition-1, we can always decide “whether we toss the item into the knapsack or not”
dp[i][n] = MAX amount of values we can get with elements [0,i] for the knapsack with capacity n
With these intuitions, we can translate them into code.
Time Complexity: O(n*c)
