Knapsack Problem please explain
Kindly Explain Knapsack Problem
@pallavigoel1996,
Knapsack problem is a DP problem.
To consider all subsets of items, there can be two cases for every item:
(1) the item is included in the optimal subset,
(2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two values.
- Maximum value obtained by n-1 items and W weight (excluding nth item).
- Value of (nth item + maximum value obtained by n-1 items) and (W - weight of the nth item) (including nth item).
If weight of nth item is > W, then the nth item cannot be included and case 1 is the only possibility.
How do you get through the approach as i don’t get the approach in DP. Have you first gone through few samples Of DP in your mind and then bcoz of that you are able to get the sol ???
@pallavigoel1996,
Dynamic programming is nothing but optimized recursion. In recursion we might encounter cases where we go through the same sub problem again and again, which leads to TLE. In DP, we store the answer of a sub problem, and when the sub problem occurs again, instead of calculating the entire answer again, we just use the answer that we calculated before.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.