Can anyone tell why My code is giving Wrong Answer for the Question “Maximizing Marks”

My Solution:

i have gone through the tutorial even looked accepted Solution for the problem…But Still Cant find and problem in My code…

Please Someone help me…

Can anyone tell why My code is giving Wrong Answer for the Question “Maximizing Marks”

My Solution:

i have gone through the tutorial even looked accepted Solution for the problem…But Still Cant find and problem in My code…

Please Someone help me…

this is 01 knapsack problem. where marks are profit and time is weight.

Yeh I know its 0/1 knapsack…

nd I have implemented it in my code…

I think you need to correct this:

Math.max(mark[i]+dp1[i-1][j-(int)time[i]], dp1[n-1][j])

Why are you considering the dp1[n-1][j] element in the loop while constructing dp1[i][j]?

2 Likes

For the normal 0/1 knapsack algo…

For checking that we are getting maximum while taking element I or by not taking element I in the knapsack…

Just change the ‘n-1’ to ‘i-1’ to get AC

1 Like

Thankx a lot…

I have been Searching for this like for 4hrs…

You’re welcome

I am facing a problem too in this question of “Maximizing Marks”. Can someone help me out:

here’s my code:

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main() {

// your code goes here

ll n,w;

cin>>n;

cin>>w;

ll arr[n],val[n],div[n];

for(ll i=0;i<n;i++){

```
cin>>val[i];
cin>>arr[i];
//div[i]=
}
ll nn=n;
ll ww=w;
ll t[nn+1][ww+1];
for(ll i=0;i<=nn;i++){
for(ll j=0;j<=ww;j++){
if(i==0 || j==0){
t[i][j]=0;
if(j==0){
t[i][j]=1;
}
}
else if(arr[i-1]<=j){
ll temp1=max((val[i-1]+t[i-1][j-arr[i-1]]),t[i-1][j]);
ll temp=(2*val[i-1]+t[i-1][j-arr[i-1]]);
t[i][j]=max(temp,temp1);
}
else{
t[i][j]=t[i-1][j];
}
}
}
```

cout<<t[nn][ww]<<"\n";

for(ll i=0;i<=nn;i++){

cout<<"\n";

for(ll j=0;j<=ww;j++){

cout<<t[i][j]<<" ";

}

}

return 0;

}