I have been trying very hard to solve the Knapsack 2 problem at E - Knapsack 2 but to no avail. I did solve the Knapsack 1 problem but just can’t solve this one. I have gone through some forums and videos where they suggest changing the state of DP, but I simply can’t understand it. Can any one please explain the reason behind state change and why it works? Any well commented code is highly appreciated.
1 Like
I haven’t solved it yet, give me some time, but consider,
what if instead of taking the most value in weight w, try the least weight needed for a value v.
4 Likes
I simply can’t find any write-up or video explaining this approach. Though I saw some videos for the problem but there they don’t go much into explaining this particular change of DP state, instead they tend to assume it as a well know matter of fact.
1 Like
Could you share your code for the problem ?? It would be better I guess.
Search on youtube… Errichto has a video
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
struct objects{
int weight,value;
};
ll solve(){
int n,w;
cin>>n>>w;
objects object[n];
int totalvalue=0;
for(int i=0;i<n;i++){
cin>>object[i].weight>>object[i].value;
totalvalue+=object[i].value;
}
ll dp[n+1][totalvalue+1];
//dp[i][j] denotes the least weight to get a value of
// j from the first i objects
dp[0][0]=0;//It takes 0 weight here
int ans=0;
for(int i=1;i<=totalvalue;i++){
dp[0][i]=1e18;
// Just set it arbitrarily large
//because it's not possible
}
for(int i=0;i<n;i++){
for(int j=0;j<=totalvalue;j++){
if(j>=object[i].value){
dp[i+1][j]=min(dp[i][j],dp[i][j-object[i].value]+object[i].weight);
//Either don't choose this object(dp[i][j]) or choose this object
//The value without it would be j-object[i].value
//the minimum weight would be the minimum weight needed to
//get a value of j- object[i].value and add the weight of this object.
}
else{
//If I choose this object the value will go over j
dp[i+1][j]=dp[i][j];
}
if(dp[i+1][j]<=w){//Is it possible to get value of j in less than w weight
ans=max(ans,j);//Find maximum such j
}
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout<<solve();
}
5 Likes
I had watched the video but could not understand it clearly. By the way, thanks for helping. 
hey i have seen some codes where this particular problem is solved by taking only one state i.e of value only. if we approach the problem in this way then dp array will go out bounds , this particular question at atcoder doesnt have that corner case. heres a link where you have got to take only one state dp. can you please help me how to solve that
Here, this will definitely help:
1 Like
I didn’t have to. I submitted my code, Only changing the input format, and it got an AC.
Also, If you want a one state dp, just remove the first index from my code, and iterate from totalvalue to 0, instead of 0 to totalvalue. The code for that is here.
It’s not neccessary and harder to intuitively visualise. The reason we have to go from total value to 0 is we are using the previous dp[i][j-object[i].value]. I don’t want this value to have already used object[i] because then I will be double counting. So we find the answer from large to small. Now that I know I won’t be double counting, I don’t need the first index.
just one more thing. how were you able to create 2d array dp[n+1][total va] when in worst case n=1001 and total value =50001
On codechef, you can easily create array of size 10^8, and that is only 5\times10^7
#include<bits/stdc++.h>
using namespace std;
long W;
long int a[1001][50001];
long int dp(int v,int i,int val[],long w[])
{ long ans;
if(v>=0)
if(a[i][v]!=-1)
return a[i][v];
if(v<=0)
ans=0;
else if(i==0 && val[i]<v)
ans= INT_MAX;
else if(i==0 && val[i]>=v)
ans=w[0];
else
ans =min(dp(v,i-1,val,w),dp(v-val[i],i-1,val,w)+w[i]);
if(v>=0)
a[i][v]=ans;
return ans;
}
int main(){
int n;
cin>>n>>W;
long int w[n];int val[n];
int sum=0;
for(int i=0;i<n;i++)
{
cin>>val[i];
sum+=val[i];
}
for(int i=0;i<n;i++)
cin>>w[i];
for(int i=0;i<1001;i++)
for(int j=0;j<50001;j++)
a[i][j]=-1;
int max=-1;
for(int i=0;i<50001;i++)
{
// cout<<“for val i=”<<i<<“min weight =”<<dp(i,n-1,val,w)<<endl;
if(dp(i,n-1,val,w)<=W)
max=i;
}
cout<<max;
Submission (39097059) for Knapsacks | HackerEarth then why is this givving memory limit exceeded
}
Please use ``` above and below your code to format it correctly.
#include<bits/stdc++.h>
using namespace std;
long W;
long int a[1001][50001];
long int dp(int v,int i,int val[],long w[])
{ long ans;
if(v>=0)
if(a[i][v]!=-1)
return a[i][v];
if(v<=0)
ans=0;
else if(i==0 && val[i]<v)
ans= INT_MAX;
else if(i==0 && val[i]>=v)
ans=w[0];
else
ans =min(dp(v,i-1,val,w),dp(v-val[i],i-1,val,w)+w[i]);
if(v>=0)
a[i][v]=ans;
return ans;
}
int main(){
int n;
cin>>n>>W;
long int w[n];int val[n];
int sum=0;
for(int i=0;i<n;i++)
{
cin>>val[i];
sum+=val[i];
}
for(int i=0;i<n;i++)
cin>>w[i];
for(int i=0;i<1001;i++)
for(int j=0;j<50001;j++)
a[i][j]=-1;
int max=-1;
for(int i=0;i<50001;i++)
{
// cout<<"for val i="<<i<<"min weight ="<<dp(i,n-1,val,w)<<endl;
if(dp(i,n-1,val,w)<=W)
max=i;
}
cout<<max;
}
The question doesn’t seem to have any testcases with total value >3*10^4 which is small enough to create an array, So pure luck.
dude, in this if we are taking ith element then value should have been added no?
dp[i+1][j]=min(dp[i][j],dp[i][j+object[i].value]+object[i].weight);
sorry but i’m still not getting 
Link to E-Knapsack 2:- https://www.youtube.com/watch?v=64W0S_G2yb8 (Learn a different approach to solve knapsack)
1 Like