- Dynamic programming
- Knapsack problem 0-1,
- Every value has weight, one value can be picked once.
- Ayush Pandey is explaining same in terms of money you are putting and profit you get by that.
- How to solve this using Dynamic programming
- Create a 2D array
- Add one extra element to handle thebase_case
- Bottom_Up needs base case, in that we go from 0 to top.
- The first row and column are 0 since the profit is going to be 0 irrespective of the prices of items.
- How are profit and weight getting mapped in the grid above?
- profits, weights, target_weight
- dp[i, j] = max ((dp(i-1)(j), (profit(i-1) + dp(i-1)(j - wt(i - 1)))
- For creation of tree, think of the possibility so n-way tree is also fine.
- TC 2^n in one approach, TC (n x w), SC (n x w)