Please share me the idea of how to solve 0-N Knapsack Problem & Colorful Knapsack Problem and Vivek And Party Problem. It seems that i am not able to think of such problem’s solution. Please help me.
0 N Knapsack Problem
Hi
These questions are based on Dynamic programming and recursion.
Please watch video of DP and recursion first and then try them,
Try to do question jo video mei krwaye h
To solve recursion questions, first create a recursive equations and base cases, then to optimise it use DP
in case problem ho rhe h or bhi …do post we’ll try to discus more about it
Hit like if you get it!
Cheers!
sir i have seen video and got the idea of 0 1 knapsack Problem but not able to do 0 N knapsack Problem.
Hi
ts an unbounded knapsack problem as we can use 1 or more instances of any resource. A simple 1D array, say dp[W+1] can be used such that dp[i] stores the maximum value which can achieved using all items and i capacity of knapsack. Note that we use 1D array here which is different from classical knapsack where we used 2D array. Here number of items never changes. We always have all items available.
We can recursively compute dp[] using below formula
dp[i] = 0
dp[i] = max(dp[i], dp[i-wt[j]] + val[j]
where j varies from 0
to n-1 such that:
wt[j] <= i
result = d[W]
Hit like if you get it!
Cheers!
Check my code for reference if you need
Hi
if you doubt is cleared please mark it resolved in your online course, or if your still have doubt do post it.
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.
can you please explain that in line no 22 you have written
k=max(k,dp[i-w[j]]+v[j]);
what is this line for