Help in Maximizing Marks

general
1

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…

2

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

3

Yeh I know its 0/1 knapsack…
nd I have implemented it in my code…

4

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
5

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…

6

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

1 Like
7

Thankx a lot… :slight_smile:
I have been Searching for this like for 4hrs…

8

You’re welcome :slight_smile:

9

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;
}