Bhaiya this series is just amazing .... pure material for cp peeps.... but due to endsems I along with many students are now not able to continue with this. So I request you to post every video at higher level only inspite if it's viewership. And I promise that I will covet this after my endsems.❤❤
I solved this problem using the traditional pick and not pick method, my dp state was different. But as i went into array descriptions, i started getting clueless. Deciding on a dp state is actually a nice problem. Great series!
hi might be a silly question but Time complexity is n.x = 10^3 * 10^5 = 10^8 why is it not giving TLE? afaik max limit allowed is 10^6 for such questions isn't it? or it is not necessary?
Your course is truly impressive, and the explanation method is excellent. I hope you consider developing courses on other topics, such as number theory and range graphs, explained in the same manner.
Surely. However, that would take a lot of time with our current bandwidth. We have our upcoming TLE 9.0 course coming up and all these topics will be covered in Level 3 and 4, you can consider that if you're interested in learning these topics.
One observation if we reverse our jth loop from x to 0, the code will run perfectly and if we think deeply the way of filling our prev and curr array... then we will realize that there is no need of internal curr array as well. We can use Prev array again for next iteration. I have changed your code to, which I explained above. vector prev(x + 1, 0); for (int i = 1; i =0 ; j--) { int w = weight[i - 1]; int value = val[i - 1]; int pick = (j >= w ? prev[j - w] + value : 0); int skip = prev[j]; prev[j] = max(skip, pick); } } cout
It works both ways as for i=0 it is base case so we get dp[1][all possible j] value giving us dp[2][all j].. so on till dp[n][all possible j]. Nice observation though>!
Yes it indeed is but according this dp state definition, dp[I][anything] makes more sense since it's already mentioned the maximum weight that we can get from a prefix of length I such that allowed capacity is W
![[CSES][Dynamic Programming] Book Shop](/img/n.gif)
This is the most effort put in a video concerning knapsack i have ever seen , keep up the good work !
Bhaiya this series is just amazing .... pure material for cp peeps.... but due to endsems I along with many students are now not able to continue with this. So I request you to post every video at higher level only inspite if it's viewership. And I promise that I will covet this after my endsems.❤❤
Yes same
I solved this problem using the traditional pick and not pick method, my dp state was different. But as i went into array descriptions, i started getting clueless. Deciding on a dp state is actually a nice problem. Great series!
hi might be a silly question but Time complexity is n.x = 10^3 * 10^5 = 10^8
why is it not giving TLE? afaik max limit allowed is 10^6 for such questions isn't it? or it is not necessary?
@@simranm.552 The bound is 10^8. 1s = 10^8. So a N*X might just pass, but there are chances of a TLE.
@@shauncrasta619 okay got it. thank you:)
Amazing video Priyansh, Every new video feels better than the previous one 🔥🔥
Thank you Priyyansh for your efforts putting into this , Hope you will continue this playlist till the end with same energy :)
UNDERSTOOD
Your course is truly impressive, and the explanation method is excellent.
I hope you consider developing courses on other topics, such as number theory and range graphs, explained in the same manner.
Surely. However, that would take a lot of time with our current bandwidth. We have our upcoming TLE 9.0 course coming up and all these topics will be covered in Level 3 and 4, you can consider that if you're interested in learning these topics.
Let's go , op series going .
day 09 too late to complete the video but not missed 😊😊
understood able to code space optimization by myself.
One observation if we reverse our jth loop from x to 0, the code will run perfectly and if we think deeply the way of filling our prev and curr array... then we will realize that there is no need of internal curr array as well. We can use Prev array again for next iteration. I have changed your code to, which I explained above.
vector prev(x + 1, 0);
for (int i = 1; i =0 ; j--)
{
int w = weight[i - 1];
int value = val[i - 1];
int pick = (j >= w ? prev[j - w] + value : 0);
int skip = prev[j];
prev[j] = max(skip, pick);
}
}
cout
It works both ways as for i=0 it is base case so we get dp[1][all possible j] value giving us dp[2][all j].. so on till dp[n][all possible j]. Nice observation though>!
Can you plz make video on CSES Problem Set after 16 videos also
Amazing content sir !
understood
understood👍
when Weight
Yes it indeed is but according this dp state definition, dp[I][anything] makes more sense since it's already mentioned the maximum weight that we can get from a prefix of length I such that allowed capacity is W
understood
Lucid !
#day9
Wont a greedy solution like profit / weight not work here at 1:56 ?
No it won't work as in this problem you can't take a book partially either you have to take it or not take it
#include
using namespace std;
int func(int n,int x,int h[],int s[],vector &dp)
{
if(n==0 || x==0)
{
return 0;
}
else if(dp[n][x]!=-1)
{
return dp[n][x];
}
else
{
int a=0;
if(n-1>=0 && x>=h[n-1])
{
a=s[n-1]+func(n-1,x-h[n-1],h,s,dp);
}
return dp[n][x]=max(a,func(n-1,x,h,s,dp));
}
}
int main()
{
int n,x;
cin>>n>>x;
int h[n],s[n];
for(int i=0;i>h[i];
}
for(int i=0;i>s[i];
}
vector dp(n+1,vector(x+1,-1));
cout
Try bottom up approach with extra space optimization that solution will be accepted